Xathrya Sabertooth

Bit Wizardry: Check and Manipulate Individual Bit

Posted: 01 Oct 2013 05:57 PM PDT

Bit Wizardry, sounds cool. Well, although the title use word wizard but we have nothing to do about magic. This article is purely about manipulating bit using bit-wise operation such as AND, OR, XOR, and SHIFT. The “magic” here is the computation where we obtain result of arithmetic operation in low-level way.

It is also known as bit hacks. This little programming trick can be a savior in optimizing the performance. Though, sometimes it is machine dependent. The operations are highly relied on bitwise operation. I assume you know all the bitwise operation.

Notation

In this article, we will use following notation for bitwise operation.

&  - bitwise and  |  - bitwise or  ^  - bitwise xor  ~  - bitwise not  << - bitwise shift left  >> - bitwise shift right

We also use some operations, such as:

+ addition  - subtraction  * multiplication  / division  % modulo

The numbers used here are 8-bit signed integers and represented as two’s complemented, unless told otherwise. The number is denoted as ‘x’ and the result operation is usually denoted as ‘y’. The individual bit of x are named b7,b6,b5,b4,b3,b2,b1,and b0 from most significant to least significant (left to right). The b7 is the sign bit.

The Tricks

#1 Check if the Integer is Even or Odd

if ((x & 1) == 0) {      // x is even  } else {      // x is odd  }

This is popular trick. The idea is that an integer is odd if and only if the least significant bit b0 is 1. It follows from the binary representation of x, where bit b0 contributes to either 1 or 0. By AND-ing x with 1 we eliminate all others bit than b0 and isolation the individual bit b0. Now, the even is defined as b0 having value 0 and odd is defined otherwise.

Let’s see the example.

00101011  &   00000001   (note: 1 is the same as 00000001)      --------      00000001

Now let’s see the -43. Remember a two’s complement number is represented as the positive one + 1. All we have to do is invert the bit andd add one. Here we have -43 is 11010101 in binary. See that the last bit is 1 therefore it is off.

Another example for 6, the binary is 00000110:

00000110  &   00000001      --------      00000000

The result is 0 which means the integer 6 is even.

#2 Test if the n-th bit is set

if (x & (1<<n)) {      // n-th bit is set  } else {      // n-th bit is not set  }

This trick is done by shifting the first bit (b0) by n positions to the left and then doing AND operation. This way, all bits but the n-th one will be clear. If the result is 0, we know that the nth bit is clear. If it is not, we know that it is set.

Here is what happens if you shift 1 several positions to the left:

1         00000001    (same as 1<<0)  1<<1      00000010  1<<2      00000100  1<<3      00001000  1<<4      00010000  1<<5      00100000  1<<6      01000000  1<<7      10000000

Now if we AND x with n-shifted 1, we effectively all the bits but n-th bit in x. See that doing n left-shift we have n zeroes on right.

Let’s see the example:

Does 123 have 3rd bit set? Let’s search the answer:

123 & (1<<3)

And, 123 is 01111011 in binary. Expression (1<<3) is 00001000.

01111011  &   00001000      --------      00001000

The answer is yes, 123 has the 3rd bit set.

Let see the -33, does it have the 5th bit set?

11011111      (-33 in binary)  &   00100000      (1<<5)      --------      00000000

The result is 0, so the 5th is not set.

#3 Set the n-th bit

y = x | (1<<n)

It use the same principal of (1<<n) trick but now we use it to set the n-th bit by shifting with OR operation. When OR-ing any values with 0 leaves the value same; but OR-in it with 1 set it to 1.

Let see the example for 120 to turn 2nd bit.

01111000    (120 in binary)  |   00000100    (1<<2)      --------      01111100

And -120 to turn 6th bit

10001000   (-120 in binary)  |   01000000   (1<<6)      --------      11001000

#4 Unset / Clear the n-th bit

y = x & ~(1<<n)

The important part is the ~(1<<n). This will set all the bits except n-th. Here how it looks:

~1        11111110  (same as ~(1<<0))  ~(1<<1)   11111101  ~(1<<2)   11111011  ~(1<<3)   11110111  ~(1<<4)   11101111  ~(1<<5)   11011111  ~(1<<6)   10111111  ~(1<<7)   01111111

Now the operation use bitwise AND. When we AND it with x, the n-th bit of x will be AND-ed to 0 which leads to 0. While the other bits will remain same.

Let’s unset the 3rd bit in 127:

01111111    (127 in binary)  &   11110111    (~(1<<3))      --------      01110111

#5 Toggle the n-th bit

y = x ^ (1<<n)

Let’s modify the 3rd trick.

The result of XOR-ing something with something else is that if both bits are the same, the result is 0, otherwise it is 1. Toggling the n-th bit means when it is 0 we change it to 1 and when it is 1 we change it to 0. Like toggling a button on and off.

Let’s see how we toggle 5th bit in 01110101:

01110101  ^   00100000      --------      01010101

What if the 5th bit originally 0?

01010101  ^   00100000      --------      01110101

One of XOR property is, when you XOR-ing the same bit twice, it return to the same value.

#6 Clear the Rightmost 1-bit

y = x & (x-1)

This trick will turn offs the rightmost one-bit. For example, given an integer 00101010 (the rightmost 1-bit is the b1) it turns it into 00101000. Or given 00010000, it turns it into 0, as there is only a single 1-bit there.

Here are more examples:

01010111    (x)  &   01010110    (x-1)      --------      01010110        01011000    (x)  &   01010111    (x-1)      --------      01010000        10000000    (x = -128)  &   01111111    (x-1 = 127 (with overflow))      --------      00000000        11111111    (x = all bits 1)  &   11111110    (x-1)      --------      11111110        00000000    (x = no rightmost 1-bits)  &   11111111    (x-1)      --------      00000000

So how can it works?

The value has the rightmost 1 bit. When we subtracting one from it sets all the lower bits to one and changes the previous rightmost 1-bit to 0. This step has masked out the rightmost 1-bit and now AND-ing it with the original value zeros that rightmost 1-bit.
The values has no rightmost 1 bit (all 0). As stated before, our case are signed integer then subtracting one will sets all bits to 1. Thus, AND-ing all zeros with all ones produces 0.

#7 Isolate the Rightmost 1-bit

y = x & (-x)

This trick finds the rightmost 1-bit and sets all the other bits to 0. For example, 01010100 gets turned into 00000100.

Here are more example:

10111100  (x)  &   01000100  (-x)      --------      00000100        01110000  (x)  &   10010000  (-x)      --------      00010000        00000001  (x)  &   11111111  (-x)      --------      00000001        10000000  (x = -128)  &   10000000  (-x = -128)      --------      10000000        11111111  (x = all bits one)  &   00000001  (-x)      --------      00000001        00000000  (x = all bits 0, no rightmost 1-bit)  &   00000000  (-x)      --------      00000000

This works because of two’s complement. In two’s complement system, -x is the same as ~x+1.

#8 Isolate the Rightmost 0-bit

This trick does the opposite of #7. It finds the rightmost 0-bit, turns off all bits, and sets this bits to 1 in the result. For example, it finds the zero in 10101011, the righmost zero is b2, and producing 00000100.

There are many ways to achieve this. For example:

#1  y = ~x & (x+1)    #2  x = ~x  y = x & -x

Now let’s see the xample:

10111100  (x)      --------      01000011  (~x)  &   10111101  (x+1)      --------      00000001        01110111  (x)      --------      10001000  (~x)  &   01111000  (x+1)      --------      00001000        00000001  (x)      --------      11111110  (~x)  &   00000010  (x+1)      --------      00000010        10000000  (x = -128)      --------      01111111  (~x)  &   10000001  (x+1)      --------      00000001        11111111  (x = no rightmost 0-bit)      --------      00000000  (~x)  &   00000000  (x+1)      --------      00000000        00000000  (x)      --------      11111111  (~x)  &   00000001  (x+1)      --------      00000001

Here’s the proof:

Suppose there is a rightmost 0-bit. Then ~x turns this rightmost 0 bit into 1 bit. And so does x+1 (because bits more right to the rightmost 0 bit are 1′s). Now AND-ing ~x with x+1 evaporates all the bits up to this rightmost 0 bit. This is the highest order bit set in the result. Now what about lower order bits to the right of rightmost 0 bit? They also got evaporated because because x+1 turned them into 0′s (they were 1′s) and ~x turned them into 0′s. They got AND-ed with 0 and evaporated.

#9 Turn on the Rightmost 0-bit

y = x | (x+1)

This hack changes the rightmost 0-bit into 1. For example, given an integer 10100011 it turns it into 10100111.

More example:

10111100  (x)  |   10111101  (x+1)      --------      10111101        01110111  (x)  |   01111000  (x+1)      --------      01111111        00000001  (x)  |   00000010  (x+1)      --------      00000011        10000000  (x = -128)  |   10000001  (x+1)      --------      10000001        11111111  (x = no rightmost 0-bit)  |   00000000  (x+1)      --------      11111111        00000000  (x)  |   00000001  (x+1)      --------      00000001

As x is OR-ed with x+1 does not lose any information, adding 1 to x fills the first rightmost 0. The result is max {x, x+1}. If x+1 overflows, it’s x and there was no 0 bits. If it doesn’t, it’s x+1 which just got rightmost bit filled with 0.

#10 Right Propagate the Rightmost 1-bit

y = x | (x-1)

This is best understood by an example. Given a value 01010000 it turns it into 01011111. All the 0-bits right to the rightmost 1-bit got turned into ones.

This is not a clean hack, tho, as it produces all 1′s if x = 0.

Let’s look at more examples:

10111100  (x)  |   10111011  (x-1)      --------      10111111        01110111  (x)  |   01110110  (x-1)      --------      01110111        00000001  (x)  |   00000000  (x-1)      --------      00000001        10000000  (x = -128)  |   01111111  (x-1 = 127)      --------      11111111        11111111  (x = -1)  |   11111110  (x-1 = -2)      --------      11111111        00000000  (x)  |   11111111  (x-1)      --------      11111111

There are two cases we can see, let’s prove from the easiest one first.

There is no rightmost 1-bit. In that case x = 0 and x-1 is -1. -1 in two’s complement is 11111111. OR-ing 0 with 11111111 produces the same 11111111. (Not the desired result, but that’s the way it is.)
There is the rightmost 1-bit b_i. Let’s divide all the bits in two groups again (like in the previous example). Calculating x-1 modifies only bits to the right, turning b_i into 0, and all the lower bits to 1′s. Now OR-ing x with x-1 leaves all the higher bits (to the left) the same, leaves bit b_i as it was 1, and since lower bits are all low 1′s it also turns them on. The result is that the rightmost 1-bit got propagated to lower order bits.

#11 Swapping two Bits

x = ((y>>k1) ^ (y>>k2)) & 1  y ^= (x<<k2)  y ^= (x<<k1)

Using this trick we can swap the k1-th bit with k2-th bit. Even if you use k1==k2, the trick can perform well and make y unchanged.

If it is known that the bits do have different values, you can make it as following:

y ^= ( (1UL<<k1) ^ (1UL<<K2) );

The 1UL in C and C++ means 1 in unsigned long representation.

Proyek Teknologi

Rabu, 02 Oktober 2013