четность установленных бит после xor двух чисел

Question

четность установленных бит после xor двух чисел

Я нашел наблюдение путем тестирования в C ++.

Наблюдение есть,

1) Если два числа, где оба числа странный количество установленных битов в нем, тогда его XOR будет иметь четное количество установленных бит в нем.

2) Если два числа, где оба числа четное количество установленных битов в нем, тогда его XOR будет иметь четное количество установленных бит в нем.

1) Если два числа где одно число имеет четное число установленных бит а также другой имеет нечетное количество установленных бит тогда его XOR будет иметь странный количество установленных бит в нем.

Я не мог доказать это. Я хочу доказать это. Пожалуйста, помогите мне.

Код, который я выполнил на моем компьютере:

#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> vec[4];
for(int i=1;i<=100;i++){
for(int j=i+1;j<=100;j++){
int x=__builtin_popcount(i)%2;
int y=__builtin_popcount(j)%2;
int in=0;
in|=(x<<1);
in|=(y<<0);
int v=__builtin_popcount(i^j)%2;
vec[in].push_back(v);
}
}
for(int i=0;i<4;i++){
for(int j=0;j<vec[i].size();j++) cout<<vec[i][j] << " ";
cout << endl;
}
return 0;
}

Это дает мне

100 нулей в первой строке
100 во второй строке
100 в третьей строке
100 нулей в четвертой строке

Если есть сомнения в понимании кода, пожалуйста, сообщите мне в комментариях.

2

c++parity xor

Решение

Другие решения

Спасибо всем, кто пытался ответить.

Мы можем предоставить доказательства, как это,

Предположим, что N — это число установленных бит в первом номере, а M — это количество установленных бит во втором номере.

Затем установите биты в XOR этих двух чисел N + M — 2 (Δ), где delta — общее количество позиций битов, где оба числа имеют биты. Теперь это выражение объясняет все.

четный + нечетный — четный = нечетный

нечетный + нечетный — четный = четный

даже + даже — даже = даже

1

xor просто очищает общие биты. Неважно, сколько бит установлено, сколько бит являются общими.

Со всеми общими битами результат равен нулю. Не имея общих битов, результатом является сумма установленных битов.

Нет выводов, основанных на четности входных данных, если только вы не учитываете четность общих битов.

0

Источник

Accepted Answer

Такое поведение отражает простой в доказательстве арифметический факт:

Когда вы добавляете два нечетных числа, вы получаете четное число,
Когда вы добавляете два четных числа, вы получаете четное число,
Когда вы добавляете нечетное число к четному числу, вы получаете нечетное число.

Учитывая этот факт, рассмотрим таблицу истинности XORи обратите внимание, что для каждого из четырех вариантов в таблице ({0, 0 => 0}, {0, 1 => 1}, {1, 0 => 1}, {1, 1, => 0}) нечетное / четное соотношение количества 1s остается инвариантным. Другими словами, если вход имеет нечетное число 1s, выход будет иметь нечетное число 1а также и наоборот.

Это наблюдение объясняет, почему вы наблюдаете результат: XORдва числа с количеством установленных битов N а также M даст число, которое имеет такое же четное / нечетное соотношение как N+M,

3