Mình xin chia sẻ lời giải bài này như sau:

• Đầu tiên, ta sẽ nhắc lại một số tính chất cơ bản của phép toán \(\oplus\) (hay còn gọi là phép XOR) như sau:

• \(a \oplus 0 = a\)

• \(a \oplus a = 0\)

Lúc này, theo đề bài ta có: \(a-(a\oplus x)-x = 0 \iff a-x = a \oplus x \iff (a-x) \oplus x = a \implies (a-x) \oplus x = (a-x)+x\)

Từ đây, quy về bài toán, tìm điều kiện của hai số không âm \(u,v\) bất kỳ thoả mãn \(u+v = u \oplus v\)

Để giải quyết được vấn đề này, đầu tiên ta có một nhận xét như sau: \(u \oplus v \le u+v\) với mọi \(u,v\) không âm.

Và điều này có thể được chứng minh như sau:

• Đặt \(u=\overline{u_1u_2...u_n}_{(2)},v=\overline{v_1v_2...v_n}_{(2)}\) (trong đó \(u_i,v_i\in \left\{0,1\right\}\))

Đến đây ta xét hai TH:

• TH1: Giả sử tồn tại chỉ số \(k(1\le k\le n)\) nào đó thoả mãn: \(u_k=v_k=1\). Khi đó ta dễ dàng suy ra được \(u+v> u \oplus v\)
• TH2: Không tồn tại chỉ số \(k(1\le k\le n)\) nào thoả mãn: \(u_k=v_k=1\). Khi đó ta có: \(u+v = u \oplus v\)

Hay nói cách khác, để \(u+v=u \oplus v\). Thì \((u_i,v_i)\in \left\{(0,1),(1,0),(0,0)\right\}\)

Lúc này, quay lại bài toán ban đầu: Ta cần tìm \(x\) sao cho \((a-x) \oplus x = a\)

Đặt \((a-x)=\overline{p_1p_2...p_n}_{(2)},x=\overline{q_1q_2...q_n}_{(2)},a=\overline{a_1a_2...a_n}_{(2)}\)

Khi đó \(a_i=1\) xảy ra khi và chỉ khi \((p_i,q_i)=(0,1)\) hoặc \((1,0)\) => Có \(2\) cách chọn để \(a_i=1\)

Và \(a_i=0\) xảy ra khi và chỉ khi \((p_i,q_i)=(0,0)\) => Có \(1\) cách chọn để \(a_i=0\)

Gọi \(e\) là số lượng số \(1\) trong biểu diễn nhị phân của số \(a\). Khi đó \(2^{e}\) chính là số nghiệm không âm của bài toán cần tìm

Để tính được \(e\) có rất nhiều cách, nhưng ở đây, mình giới thiệu hàm \(\text{__builtin_popcount(a)}\) chính là hàm trả về số lượng số \(1\) của số \(a\) trong biểu diễn nhị phân.

Như vậy là bài toán đã được giải quyết xong.

Các bạn có thể tham khảo code mình tại đây: Link

Ps: Nếu có gì khó hiểu hoặc sai sót, các bạn cứ comment nhé !