# Blog #1: Nguyên lí hoạt động của x & (-x)
**Tác giả: Phan Thành Hưng (hungg_261)**

___
### Giới thiệu
Chắc hẳn nhiều bạn cũng đã học tới cấu trúc dữ liệu ==Fenwick tree== rồi. Trong đó, nếu tinh ý bạn sẽ nhận ra dòng code sau:

x & (-x)

Vậy ý nghĩa của dòng code này là gì? Cùng mình tìm hiểu về nó trong bài blog này của mình nhé :face_with_cowboy_hat:.

___
### Định nghĩa
Biểu thức `x & (-x)` trong lập trình (phép $\&$ là phép [bitwise AND](https://wiki.vnoi.info/algo/basic/bitwise-operators.md#to%C3%A1n-t%E1%BB%AD-bitwise-and-or-v%C3%A0-xor)) giúp lấy ra bit 1 thấp nhất (least significant bit, aka. bit 1 nằm ngoài cùng phía bên phải) được bật (set) trong số nguyên`x`.
Ví dụ như ta có số sau (dưới dạng nhị phân): $\text{x} = 101100_2$ thì $\text{x & (-x)}$ sẽ trả ra $000100_2$ là bit 1 thấp nhất của $\text{x}$.

### Giải thích
Vậy nguyên lí hoạt động của biểu thức này là gì, tại sao `x & (-x)` lại có thể trả ra kết quả được như vậy??? Tại sao lại có số âm trong đây??

>[!Note] Cách C++ biểu diễn số âm bằng bit
> Trước hết, ta cần hiểu cách C++ (và nhiều ngôn ngữ khác) xử lí số âm với bit. Để chuyển từ $\text x$ thành $- \text x$ thì C++ sẽ lật hết các bit lại (aka. flip - từ 1 thành 0, từ 0 thành 1), sau đó cộng 1 vào số mới sau khi lật đó. Cụ thể hơn, nếu `~` là toán tử bitwise dùng để lật (flip) hết toàn bộ bit trong một số, thì: $-\text x = (\sim \text {x}) + 1$
> Ta có thể chạy đoạn code sau để kiểm chứng:
> ```cpp
> #include<bits/stdc++.h>
> using namespace std;
>
> signed main(){
> ios_base::sync_with_stdio(0);cin.tie(0);
>
> int x = 5;
> int new_x = (~x) + 1;
>
> cout << "x = " << x << '\n';
> cout << "-x = " << -x << '\n';
> cout << "(~x) + 1 = " << new_x << '\n';
>
> return 0;
> }
> ```
> Có thể thấy output của $-\text x$ và $($~$\text {x}) + 1$ là giống nhau.
> **Lưu ý:** đây là quy ước rồi nên mình không cần chứng minh nhé :+1:

**Vậy tại sao công thức lại đúng?**
Đặt biểu diễn nhị phân $k$-bit của $\text x$ là $\overline{a_1a_2...a_k}\ \ (a_i \in \{0,1\})$.
Ví dụ với kiểu dữ liệu `int` thì $k=32$, còn `long long` thì $k=64$.

Giả sử bit 1 nhỏ nhất nằm ở vị trí $i$, lúc này $\text x$ sẽ trở thành:
$$
\overline{a_1a_2...a_i\ \underbrace{00...0}_{k-i}}
= \overline{a_1a_2...1\ \underbrace{00...0}_{k-i}}
$$
Tất cả $k-i$ bit nằm sau $a_i$ bắt buộc phải là $0$ do $a_i$ là bit 1 thấp nhất.
Để thuận tiện, ta đặt $A$ là một biểu diễn nhị phân và $A=\overline{a_1a_2...a_{i-1}}$. Lúc này $\text x$ được viết lại thành:
$$
\text x = \overline{A\ 1\ \underbrace{00...0}_{k-i}}
$$

Như mình đã nói ở trên, nếu đảo dấu thì ta flip hết các bit và cộng 1. Trước hết, ta thực hiện thao tác flip hết các bit của $\text x$, $\text x$ trở thành:
$$
\sim \text x = \overline{(\sim A)\ 0\ \underbrace{11...1}_{k-i}}
$$ Đừng quên $\sim$ là thao tác flip hết các bit trong một biểu diễn nhị phân.
Sau đó, ta thực hiện bước tiếp theo (cộng 1 vào giá trị sau khi đã được flip bit), lúc này $\text x$ là:
$$
(\sim \text x) + 1 = -\text x = \overline{(\sim A)\ 1\ \underbrace{00...0}_{k-i}}
$$

Cuối cùng, ta thực hiện phép bitwise AND ($\&$) giữa $\text x$ và $-\text x$:
$$
\text x\ \&\ (-\text x) = \overline{A\ 1\ \underbrace{00...0}_{k-i}}\quad \&\quad \overline{(\sim A)\ 1\ \underbrace{00...0}_{k-i}}
$$
Thực hiện theo từng phần một, ta có:
- $A\ \&\ (\sim A) = \underbrace{00...0}_{i-1}$
- $1\ \&\ 1 = 1$
- $\underbrace{00...0}_{k-i}\quad\&\quad \underbrace{00...0}_{k-i}\ \ =\ \ \underbrace{00...0}_{k-i}$

Ghép các kết quả có được, ta được:
$$
\text x\ \&\ (-\text x) = \overline{A\ 1\ \underbrace{00...0}_{k-i}}\quad \&\quad \overline{(\sim A)\ 1\ \underbrace{00...0}_{k-i}}
$$

$$
= \overline{\underbrace{00...0}_{i-1}\ 1\ \underbrace{00...0}_{k-i}}
$$

Có thể thấy, bit 1 duy nhất còn lại chính là bit nằm ở vị trí $i$, là $a_i$, chính là bit 1 thấp nhất. Vậy biểu thức `x & (-x)` trả ra bit 1 thấp nhất của `x`.