Finding out number of bits that have changed (bitwise operator)

Question

I have a bit string that is generated based on user input. I also have another bit string that I use to perform bitwise & with the generated bit string. What I would like to know is how to find out how many bits of the generated bit string has changed from the & operation. So let say if I have 10000101 as generated bit string and 00101111 as a second bit string I use for & operation. The output of the process should be 1 since only the first bit of the generate bit string has changed. How do I do that?

It should be easy to just loop over the bits of the generated bit-string and compare with the original, no? — OneCricketeer, Apr 12 '16 at 18:11

score 2 · Answer 1 · answered Apr 12 '16 at 18:06

2

What you are looking for is bitwise XOR (exclusively OR), or a^b:

   10000101 ^ 00101111 → 10101010

Is is logically equivalent to (~a&b) | (a&~b)

answered Apr 12 '16 at 18:06

Maljam

6,244
3
17
30

score 1 · Accepted Answer · edited May 23 '17 at 10:34

1

You need to XOR the result with the original to identify which bits were changed:

changedBits = (userInput & generatedInput) ^ userInput

Then, you need to calculate the Hamming Weight of the changedBits value:

int hammingWeight(int i) {
     i = i - ((i >>> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
     return (((i + (i >>> 4)) & 0x0F0F0F0F) * 0x01010101) >>> 24;
}

int numberOfChangedBits = hammingWeight(changedBits);

Adjust as needed depending on how many bits your inputs are.

edited May 23 '17 at 10:34

Community

1
1

answered Apr 12 '16 at 18:11

Darth Android

3,437
18
19

Awesome! That's the answer I'm looking for. – user3273345 Apr 12 '16 at 20:11
@harold : Thanks for the tip! – user3273345 Apr 12 '16 at 20:11

Finding out number of bits that have changed (bitwise operator)

2 Answers2