3

I have to create a function bitParity(int x) that takes an integer and returns 1 if there is an odd number of 0's in the bit form of x, and 0 otherwise.

Ex: bitParity(5) = 0, bitParity(7) = 1

However, this is difficult as I can only use bit operators on this problem (! ˜ & ˆ | + << >> are the only legal ones). That means, no loops, if-then, or anything of the sort. Constants can be used.

So far, what I have doesn't work, but I figured that I should shift the bits of the integer 16, 8, and 4 times and XOR the remaining integers.

Can anyone offer some advice? Thanks.

Kamyar Souri
  • 1,871
  • 19
  • 29
Dennis
  • 47
  • 2
  • 3
  • 5
  • 3
    First place you should always check for bitwise examples is here http://graphics.stanford.edu/~seander/bithacks.html#ParityLookupTable <- Bookmark that. You should however make a decent effort on your own and post what you have done. Since this is homework you should make sure you have a full understanding of whats going on and not just copy and paste code from that link. – Joe Feb 03 '12 at 18:06
  • A lookup table is the best way. 256 bytes of storage is a small price to pay. If you're working with 32-bit integers, just read from the table 4 times. – BitBank Feb 03 '12 at 18:09
  • 1
    Other than what @Joe has mentioned, you may refer http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know also. This has some primitive bit hacks which I find it useful. – Sangeeth Saravanaraj Feb 03 '12 at 18:11
  • 1
    check this out https://stackoverflow.com/a/21618038/2672154 – tf3 Feb 01 '21 at 04:22

3 Answers3

9

For 32bit numbers: 

function bitParity(int x) {
   x ^= x >> 16;
   x ^= x >> 8;
   x ^= x >> 4;
   x &= 0xf;
   return (0x6996 >> x) & 1;
}

Note* 0x6996 represents a bit vector of the numbers 1, 2, 4, 7, 8, 11, 13, and 14. All of the 4-bit values that can be represented by an odd number of bits. In 0x6996, a bit is set if its position in the vector corresponds with (1, 2, 4, 7, 8, 11, 13, or 14).

This is why (0x6996 >> x) & 1 makes sense, after the shift by x, this expression will only result in a returned 1 if x is equal to any of the values in the bit vector, meaning an odd number of bits were set.

Baruch
  • 87
  • 6
Rudu
  • 15,682
  • 4
  • 47
  • 63
  • 2
    Magic explained: after `x ^= x>>16`, the low 16 bits have the same parity as the original. Two more lines, and you have 4 bits with the correct parity. After `&=` you have a number between 0 and 15 (with the correct parity). `0x6996` serves as a lookup table - for each number between 0 and 15 you choose one of its bits. – ugoren Feb 03 '12 at 18:25
  • @Joe - As ugoren has explained `0x6996` is a tiny lookup table ;) This is just an ultra-efficient way to do it, and requires *lots* of understanding... but it works. – Rudu Feb 03 '12 at 18:28
6

This is properly solved with a loop. But here is a way to do it without.

x = (x & 0x0000FFFF) ^ (x >> 16)
x = (x & 0x000000FF) ^ (x >> 8)
x = (x & 0x0000000F) ^ (x >> 4)
x = (x & 0x00000003) ^ (x >> 2)
x = (x & 0x00000001) ^ (x >> 1)

Edit: I don't need the &. A better version:

x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
x &= 1;
Kendall Frey
  • 43,130
  • 20
  • 110
  • 148
  • Thank you so much! I was extremely close, but missed the last x&1. Could you give me a little insight as to how you came to this conclusion? Thank you. – Dennis Feb 03 '12 at 18:55
  • I'm not sure. I was thinking through it, and I had a brain wave. My first thought was XORing all the bits, one at a time. But that would be ugly. This way I visualize it as folding the number onto itself repeatedly. – Kendall Frey Feb 03 '12 at 19:45
0

Here's one of my functions that I used during my work on bachelor thesis ;)

/** Calculates number of bits in unsigned char
 * @brief Bit count
 * @param input to be checked
 * @return int 0-8
 */
int bitCount( unsigned char input)
{
    static unsigned char count[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
    return (int)(
            count[ input & 0x0f] +
            count[ (input >> 4) & 0x0f]
    );
}

So total count for 4B integer would be:

int bytes = bitCount( (unsigned char)((number >> 0)&255))
            + bitCount( (unsigned char)((number >> 8)&255))
            + bitCount( (unsigned char)((number >> 16)&255))
            + bitCount( (unsigned char)((number >> 24)&255));

And parity:

 return bytes%2;
 return bytes&1; // if you preffer

I always wanted to reuse those codes :)

EDIT: As you may noticed unsigned char (8b) can be split into 2 pieces each 4b long, that means 16 values which are easy to store and reuse. So you take first 8b from integer, split them into two pieces. Make sure them are both in interval <0,15>, and just directly get bit count. Repeat :)

Vyktor
  • 20,559
  • 6
  • 64
  • 96