Problem
Word’s Parity
The parity of a binary word is 1 if the number of 1s in the word is odd; otherwise, it is 0. e.g., the parity of 1011 is 1, and the parity of 10001000 is 0. How would you compute the parity of a very large number of 64-bit words?
Solution
- >> is the signed right shift
- >>> is the unsigned right shift
- right shift is equal to divid by 2.
- &1 will get the LSB of the binary number.
- 0^0 get 0
- 0^1 get 1
- 0b1000001 is binary number representation
- binary can be assigned to long without cast
public class WordParity {
public static short parity(long x) {
short count = 0;
while(x != 0) {
count ^= (x&1);
x = x>>>1;
}
return count;
}
public static void main(String...args) {
System.out.println(parity(0b101100000000000000));
System.out.println(parity(0b1101110100110));
}
}
public static short parity(long x) {
short count = 0;
while(x != 0) {
count ^= (x&1);
x = x>>>1;
}
return count;
}
public static void main(String...args) {
System.out.println(parity(0b101100000000000000));
System.out.println(parity(0b1101110100110));
}
}
The time cost is O(bits of the number), space cost is O(1).
