четность установленных бит после xor двух чисел - PullRequest
Новая
       48

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

0 голосов
/ 20 мая 2018

Я обнаружил наблюдение путем тестирования на 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 нулей в четвертой строке

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

Ответы [ 3 ]

0 голосов
/ 20 мая 2018

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

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

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

0 голосов
/ 20 мая 2018

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

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

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

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

четное + нечетное - четное = нечетное

нечетное + нечетное - четное = четное

четное + четное - четное = четное

0 голосов
/ 20 мая 2018

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

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

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

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

...