# Bit Wizardry: Check and Manipulate Individual Bit

Home / Bit Wizardry: Check and Manipulate Individual Bit

### Bit Wizardry: Check and Manipulate Individual Bit

December 9, 2015 | Article | No Comments

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

```&  - 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?

1. 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.
2. 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.

1. 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.)
2. There is the rightmost 1-bit bi. 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 bi 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 bi 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.