CODEWITHSUNDEEP
javaalgorithmbit-manipulation
user6276737
user6276737

Reputation:

Computing the parity of a binary word

I have the following code that computes the parity of a binary word:

    public class Parity1 {

      public static short parity(long x) {

        short result = 0;
        while (x != 0) {
          result ^= (x & 1);

          x >>>= 1;

        }
        return result;

      }

If I have odd numbers of ones like 1011, I will get 1 and otherwise like 100001000, I will get 0.However, I am not seeing how the code is working.If I take 1011, and I pass it then I get the following:

    number:1011
    result : 0
    result xor (1&1) == 1=>result
    x >>>=1 => 0101
    ----------------------
    number:0101
    result : 1
    result xor (1&1) == 0 => result 
    x >>>=1 => 0010
    ----------------------
    number :0010
    result : 0
    result xor (0&1) ==0 => result
    x >>>=1 => 0001
    ------------------------
    number :0001
    result : 0
    result xor (1&1) ==1 => result
    x >>>=1 => 0000
   ------------------------

    number :0000
    result : 1
    result xor (1&1) ==1 => result
    while (x!=0) but x(number) is 0
    ends with result 0.

Can someone please explain what I am missing?

Edit

Here is another method that does the same thing but efficiently. However,I'm not getting it too either.

    public static short parity(long x){

        short result =0;


  while (x!=0){
    result ^=1;
    x &= (x-1);
    }
    return result;
    }

Upvotes: 2

Views: 1711

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

The code that you've posted looks correct, which leads me to think that you might be invoking it incorrectly. You gave 1011 as an example of a number where the parity should be 1 even though you're getting 0. If you use the binary number 1011 (decimal: 11), then you should get 1, but if you use the decimal number 1,011 (one thousand eleven), then you should get 0 because its binary representation is

1111110011

which has an even number of 1s in it.

If you want to invoke the function with the binary number 1011, invoke it as

parity(0b1011)

rather than

parity(1011).

Upvotes: 3

Related Questions