# 476. Number Complement

# 1. Tóm tắt đề bài

Cho một số nguyên dương $n$. Xét số đó ở dạng nhị phân, ta cần đảo hết bit của số này và trả về dạng thập phân của kết quả.

##### Giới hạn

$1 \le n < 2^{31}$

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(log(n))$**

Đây là một bài toán không quá khó để cài đặt, khi mà các bạn chỉ cần làm đúng theo hướng dẫn để ra được kết quả.

Tuy nhiên, key ở đây là các bạn cần phải xử lý tốt bài toán sử dụng các [toán tử bitwise](https://vi.wikipedia.org/wiki/Ph%C3%A9p_to%C3%A1n_thao_t%C3%A1c_bit).

# 3. Lời giải chi tiết

Ban đầu, đặt `bit` là $1$. Biến này sẽ tương ứng với vị trí bit bạn đang xét trong $n$.

Lặp lại cho đến khi `bit` vượt quá giá trị của $n$:

- $n := bit\ XOR\ n$.
- $bit := bit << 1$ (dịch phải 1 bit, tương đương với phép `*= 2`)

### Độ phức tạp thuật toán

Thời gian: $O(log(n))$

Bộ nhớ mở rộng: $O(1)$