Programming June 30, 2009

# Low Level Bit Hacks You Absolutely Must Know

I decided to write an article about a thing that is second nature to embedded systems programmers - low level bit hacks. Bit hacks are ingenious little programming tricks that manipulate integers in a smart and efficient manner. Instead of performing some operation (such as counting the 1 bits in an integer) by looping over individual bits, these programming nuggets do the same with one or two carefully chosen bitwise operations.

To get things going I'll assume that you know what the two's complement binary representation of an integer is and also that you know all the the bitwise operations.

I'll use the following notation for bitwise operations in the article:

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

The numbers in the article are 8 bit signed integers (though the operations work on arbitrary length signed integers) that are represented as two's complement and they are usually named 'x'. The result is usually 'y'. The individual bits of 'x' are named b7, b6, b5, b4, b3, b3, b2, b1 and b0. The bit b7 is the sign bit (the most significant bit), and b0 is the least significant.

I'll start with the most basic bit hacks and gradually progress to more difficult ones. I'll use examples to explain how each bithack works.

If you are intrigued by this topic I urge you to subscribe to my blog. I can share a secret that there will be the 2nd part of this article where I cover more advanced bit hacks, and I will also release a cheat sheet with all these bit tricks! It's well worth subscribing!

Here we go.

Bit Hack #1. Check if the integer is even or odd.

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

I am pretty sure everyone has seen this trick. The idea here 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 the other bits than b0. If the result after this operation is 0, then 'x' was even because bit b0 was 0. Otherwise 'x' was odd.

Let's look at some examples. Let's take integer 43, which is odd. In binary 43 is 00101011. Notice that the least significant bit b0 is 1 (in bold). Now let's AND it with 1:

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

See how AND-ing erased all the higher order bits b1-b7 but left bit b0 the same it was? The result is thus 1 which tells us that the integer was odd.

Now let's look at -43. Just as a reminder, a quick way to find negative of a given number in two's complement representation is to invert all bits and add one. So -43 is 11010101 in binary. Again notice that the last bit is 1, and the integer is odd. (Note that if we used one's complement it wouldn't be true!)

Now let's take a look at an even integer 98. In binary 98 is 1100010.

```    01100010
&   00000001
--------
00000000
```

After AND-ing the result is 0. It means that the bit b0 of original integer 98 was 0. Thus the given integer is even.

Now the negative -98. It's 10011110. Again, bit b0 is 0, after AND-ing, the result is 0, meaning -98 is even, which indeed is true.

Bit Hack #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
}
```

In the previous bit hack we saw that (x & 1) tests if the first bit is set. This bit hack improves this result and tests if n-th bit is set. It does it by shifting that first 1-bit n positions to the left and then doing the same AND operation, which eliminates all bits but n-th.

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 1 shifted n positions to the left we effectively eliminate all the bits but n-th bit in 'x'. If the result after AND-ing is 0, then that bit must have been 0, otherwise that bit was set.

Let's look at some examples.

Does 122 have 3rd bit set? The operation we do to find it out is:

```122 & (1<<3)
```

Now, 122 is 01111010 in binary. And (1<<3) is 00001000.

```    01111010
&   00001000
--------
00001000
```

We see that the result is not 0, so yes, 122 has the 3rd bit set.

Note: In my article bit numeration starts with 0. So it's 0th bit, 1st bit, ..., 7th bit.

What about -33? Does it have the 5th bit set?

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

Result is 0, so the 5th bit is not set.

Bit Hack #3. Set the n-th bit.

```y = x | (1<<n)
```

This bit hack combines the same (1<<n) trick of setting n-th bit by shifting with OR operation. The result of OR-ing a variable with a value that has n-th bit set is turning that n-th bit on. It's because OR-ing any value with 0 leaves the value the same; but OR-ing it with 1 changes it to 1 (if it wasn't already). Let's see how that works in action:

Suppose we have value 120, and we wish to turn on the 2nd bit.

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

What about -120 and 6th bit?

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

Bit Hack #4. Unset the n-th bit.

```y = x & ~(1<<n)
```

The important part of this bithack is the ~(1<<n) trick. It turns on all the bits except n-th.

Here is 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
```

The effect of AND-ing variable 'x' with this quantity is eliminating n-th bit. It does not matter if the n-th bit was 0 or 1, AND-ing it with 0 sets it to 0.

Here is an example. Let's unset 4th bit in 127:

```    01111111    (127 in binary)
&   11101111    (~(1<<4))
--------
01101111
```

Bit Hack #5. Toggle the n-th bit.

```y = x ^ (1<<n)
```

This bit hack also uses the wonderful "set n-th bit shift hack" but this time it XOR's it with the variable 'x'. The result of XOR-ing something with something else is that if both bits are the same, the result is 0, otherwise it's 1. How does it toggle n-th bit? Well, if n-th bit was 1, then XOR-ing it with 1 changes it to 0; conversely, if it was 0, then XOR-ing with with 1 changes it to 1. See, the bit got flipped.

Here is an example. Suppose you want to toggle 5th bit in value 01110101:

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

What about the same value but 5th bit originally 0?

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

Notice something? XOR-ing the same bit twice returned it to the same value. This nifty XOR property is used in calculating parity in RAID arrays and used in simple cryptography cyphers, but more about that in some other article.

Bit Hack #6. Turn off the rightmost 1-bit.

```y = x & (x-1)
```

Now it finally gets more interesting!!! Bit hacks #1 - #5 were kind of boring to be honest.

This bit hack turns off the rightmost one-bit. For example, given an integer 00101010 (the rightmost 1-bit in bold) it turns it into 00101000. Or given 00010000 it turns it into 0, as there is just a single 1-bit.

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

Why does it work?

If you look at the examples and think for a while, you'll realize that there are two possible scenarios:

1. The value has the rightmost 1 bit. In this case subtracting one from it sets all the lower bits to one and changes that rightmost bit to 0 (so that if you add one now, you get the original value back). This step has masked out the rightmost 1-bit and now AND-ing it with the original value zeroes that rightmost 1-bit out.

2. The value has no rightmost 1 bit (all 0). In this case subtracting one underflows the value (as it's signed) and sets all bits to 1. AND-ing all zeroes with all ones produces 0.

Bit Hack #7. Isolate the rightmost 1-bit.

```y = x & (-x)
```

This bit hack finds the rightmost 1-bit and sets all the other bits to 0. The end result has only that one rightmost 1-bit set. For example, 01010100 (rightmost bit in bold) gets turned into 00000100.

Here are some more examples:

```    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 bit hack works because of two's complement. In two's complement system -x is the same as ~x+1. Now let's examine the two possible cases:

1. There is a rightmost 1-bit bi. In this case let's pivot on this bit and divide all other bits into two flanks - bits to the right and bits to the left. Remember that all the bits to the right bi-1, bi-2 ... b0 are 0's (because bi was the rightmost 1-bit). And bits to the left are the way they are. Let's call them bi+1, ..., bn.

Now, when we calculate -x, we first do ~x which turns bit bi into 0, bits bi-1 ... b0 into 1s, and inverts bits bi+1, ..., bn, and then we add 1 to this result.

Since bits bi-1 ... b0 are all 1's, adding one makes them carry this one all the way to bit bi, which is the first zero bit.

If we put it all together, the result of calculating -x is that bits bi+1, ..., bn get inverted, bit bi stays the same, and bits bi-1, ..., b0 are all 0's.

Now, AND-ing x with -x makes bits bi+1, ..., bn all 0, leaves bit bi as is, and sets bits bi-1, ..., b0 to 0. Only one bit is left, it's the bit bi - the rightmost 1-bit.

2. There is no rightmost 1-bit. The value is 0. The negative of 0 in two's complement is also 0. 0&0 = 0. No bits get turned on.

We have proved rigorously that this bithack is correct.

Bit Hack #8. 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
```

Let's prove it, though not as rigorously as in the previous bithack (as it's too time consuming and this is not a scientific publication). There are two cases again. Let's start with easiest 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.

Bit Hack #9. Isolate the rightmost 0-bit.

```y = ~x & (x+1)
```

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

More examples:

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

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.

Bit Hack #10. 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 examples:

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

Here is the proof as a bunch of true statements. OR-ing x 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 were no 0 bits. If it doesn't, it's x+1 which just got rightmost bit filled with 1.

## Bonus stuff.

If you decide to play more with these hacks, here are a few utility functions to print binary values of 8 bit signed integers in Perl, Python and C.

Print binary representation in Perl:

```sub int_to_bin {
my \$num = shift;
print unpack "B8", pack "c", \$num;
}
```

Or you can print it from command line right away:

```perl -wle 'print unpack "B8", pack "c", shift' <integer>

# For example:
perl -wle 'print unpack "B8", pack "c", shift' 113
01110001

perl -wle 'print unpack "B8", pack "c", shift' -- -128
10000000
```

Print binary number in Python:

```def int_to_bin(num, bits=8):
r = ''
while bits:
r = ('1' if num&1 else '0') + r
bits = bits - 1
num = num >> 1
print r
```

Print binary representation in C:

```void int_to_bin(int num) {
char str[9] = {0};
int i;
for (i=7; i>=0; i--) {
str[i] = (num&1)?'1':'0';
num >>= 1;
}
printf("%s\n", str);
}
```

Have fun with these! I'll write about advanced bit hacks some time soon. If you are really intrigued by this topic I encourage you to subscribe to my blog. Thanks!

Ps. Let me know in the comments what you think about this article, and let me know if you do not know what two's complement, or the basic binary operations are. If there are a few people who would like me to explain these concepts, I'll be glad to write another article just about these fundamental topics.

Pps. There is a book entirely on bit hacks like these. It's called "Hacker's Delight". It may be worth getting if you are into this stuff.

Nice and very useful tips. I have another one to add to your collection :) Sometimes ago I have learned how to convert binary to decimal in mind very easily. You only need to remember first 8 numbers:
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7

Then, you need to know that shifting to left by one digit multiplies the number by 2:
1010b = 101b x 10b = 5 x 2 = 10d
10100b = 101b x 100b = 5 x 8 = 40
So, when you see something like 101011, you can process it this way:
101000b + 11b = 5 * 8 + 3 = 43
1110101 = 7 * 16 + 5 = 117
and so on.

It's easier than it looks at first glance :)

I like this hack... I discovered it independently too during an exam during my last semester... The course was on digital logic design. We were given a very long binary number (more than 12 digits) and the use of calculators weren't permitted. While most people used the traditional method (place value), I used bit shifting thanks to my programming background :-)

Your second example (the one ending with = 40) is wrong, it equals 20 (5 x 4)

BTW, "10100b = 101b x 100b = 5 x 8 = 40" should be "5x2 =20".
Sincerely
Sushil

Your python code has an error

`while b:`

should be

`while bits:`

Nice entry-level tutorial; but, excuse me - "hacks"?

Sorry to nit-pick, but since you're trying to teach worthwhile and legitimate C.S. topics, why reach for the most tired of all techno-marketing-isms: hack.

If the term is truly to have no meaning whatsoever anymore (yes, it's worn out) -- then let's just quit using it.

I agree with you to some extent although I do not consider this Computer _Science_. If people keep saying C.S. to every little programming related thing they find then we will find ourselves the laughing stock of the scientific community.

bit-hacks is a canonical term for this type of thing.

Bit fiddling.

The authors of HAKMEM would like a word with you.

George Boole would like a word with authors of HAKMEM.

Awesome post! I wish all high school binary education included these gems. I was able to immediately use the more boring hacks (#3 and #4) for my i2c controlled piano lightbar project in converting it to use an arduino. And to think for a second I was going to write some horrible function in C to do this.

All hail the uber bit hacks!!

no

vik, nice trick. The way I count in binary is I add powers of two quickly. For example: 1110101 is 64 + 32 + (16 + 4) + 1 = 96 + 20 + 1 = 116 + 1 = 117. Your trick is much quicker tho. I am going to master it!

Matt, thanks, I had 'b' everywhere before I turned into 'bits'. Corrected now!

Justin, I was inspired by "Hacker's Delight" book. It calls them all hacks because they come from MIT where this term was coined and these operations were originally considered very smart programming tricks thus hacks. I decided to honor MIT and the book and called them hacks in my article as well.

techninja42, great to find that you found them immediately useful!

Please also check this out for lot of bit hacks:
http://graphics.stanford.edu/~seander/bithacks.html

Thanks for the article Peter.

It's always good to review this stuff, I just I could recognise the opportunities to use it a bit more often.

It's always good to go over again (and again) though.

Thanks

Great article! Just one thing though. Unless I'm doing my math wrong, -43 should be "11010101", not "11101011". :)

Sorry, but Justin Thyme has it right. These are not hacks, but basic coding chunks that anyone with a knowledge of the operator functions will figure out. Not saying it isn't useful, but it certainly isn't deep or hackish.

No, "Justin Thyme" is an ignorant troll and so are you.

Hey, good trick Vik,
But I think you made a typo in the following:
10100b = 101b x 100b = 5 x 8 = 40

The correct answer should really be
10100b = 101b x 100b = 5 x 4 = 20

So what's your trick for "counting the 1 bits in an integer" that you mentioned in the intro as the canonical example of where not to loop over the individual bits?

For your information, another interesting related page is the list of Bit Twiddling Hacks.

Nice post!

Printing binary numbers in python is quite straight-forward:

print bin(1234) # or use bin(1234)[2:] to trim the '0b'

Nice article Peter !
That book is interesting , I'm aware of it , but these tricks are much older, they are also presented this book.

Arun, that doesn't work for negative numbers and it also does not left-fill with 0's. It also works only in Python >= 2.6. For negatives it produces bin(-x) = -bin(x).

Alex Epshteyn, I'll write about that trick in the next part of the article, called "advanced bit hacks". It's pretty complicated.

Other Alex, thanks for catching that -43 mistake. I have now fixed it in the article!

Another bit-based operation:
Switch values of a and b w/o using additional variable

`a^=b;b^=a;a^=b;`

This is undefined behaviour (i.e. implementation dependent) in C/C++ and it doesn't work in Java.

here you go: a=a^b; b=a^b; a=a^b;

This could play hell with the CPU's pipeline. I think the best way to go is to simply use a temporary register.

try it when a == b :)

It works fine when a == b. That you could think it wouldn't indicates that your math intuitions are bad.

Sorry to be a party crusher, but you've got a mistake (at least one, I stopped reading.)

=========================================
Bit Hack #6. Turn off the rightmost 1-bit.

y = x & (x-1)
=========================================

Plain wrong. Any X ending with xxx10, when ANDed with (x-1), which obviously ends with xxx01, gives xxx00, ie. a number whose LAST TWO BITS ARE 0.

2d & 1d = 0
10d (0xA) & 9d (0x9) = 8.

Sorry.

Isn't the answer for Bit Hack #6 simply:

y = x & 0xFFFFFFE

(at least for 32-bit values)

I do not see any problem.

xxx10 => xxx00, so the rightmost bit is 0 after that, as advertised.

The problem is with the word 'rightmost' in the title. Like you, I initially assumed that it meant the final bit in the pattern; but what it is intended to mean is "Reset the first found bit that has a value of one when scanning from right to left", but that is a mouthful!

The affected bit in your example of 'xx10' is the '1' between the 'xx' and '0', which (as you correctly point out) is the bit that gets changed to 'xx00'. Rather than being an error, that is the intention of the hack.

No, the problem is that you and John Doe are stupid. There is nothing in the least ambiguous about "the rightmost 1-bit".

I had to go back and read Bit Hack#6 again to check, but it DOES do what it says - it turns off the *rightmost 1 bit* (that is, the last binary '1' when reading left to right), which is not necessarily the *rightmost bit* of the number.

Grammatically it isn't clear that 1 is not count but the property of the bit. I mean it could mean "turns off rightmost n bits", it is here clear that n is count, in case of 1 we can't be sure about that.

I understood it from the context but I see what 'John Doe' says.

"Grammatically it isn't clear that 1 is not count but the property of the bit."

God that's funny. Talk about grammatically unclear ...

Right, turning off the rightmost bit is this

x = n & (~1)

2 & ~1 = 2
3 & ~1 = 2

No, stupid, this is about turning off the rightmost *1-bit*.

Sorry, but you're an idiot ... turning off the rightmost 1-bit of 10 yields 00 ... duh.

An addition to my previous comment: I'm assuming you meant "Bit Hack #6. Turn off ONLY the rightmost 1-bit."

If you don't care about the other bits, then you're right, but then, of course, what's the point?

Very useful in this data structure:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Its also what led to (x & -x) when I read about it.

Nice blog post. I enjoyed it. Looking forward to the next installment.

John Doe, sure, turn off ONLY the rightmost 1-bit.

The point is you can have a situation where you need to turn off the rightmost bit. For example you have an array of LED devices and an 8 bit array controls which devices are on are which are off. And you want to turn off the rightmost device. Then there you have it.

Ps. there shouldn't be any mistakes in the article, i proof read it around 10 times and it took me several full days to write it.

Fallacy: Number of days to write and proof read an article does not ensure accuracy.

That's minimize error as intended. Nothing can ensure accuracy.

check if a number is power of 2

if ( ( n && ( n-1 ) ) == 0 )
{
//power of 2
}
else
{
//not power of 2
}

FIX: && => &

Additionally: can also be written as

(n & (-n)) == n

```>  -  bitwise shift left
```

P.S. You can't call yourself a programmer when you have this instruction for your comments:

`Please use < to insert '`

Why: ok.

Dear Peter,

I was not questioning the need for resetting the LSB. There are countless examples for that.

What I WAS saying, however, is that the expression you stated, y = x & (x-1), IS WRONG.

You may have proofread your article, but this is still a mistake. And though I have already shown you two examples in my first post, I will do that again, just so everything's clear:

Example 1:
Let X be 0101010b / 02Ah / 42d.
Let y = x & (x-1):
(0101010 & 0101001) / (02Ah & 029h)
y equals 0101000 / 028h.
Not only was the LSB reset,
but the bit at n=1 as well.

Example 2:
Let X be 10b / 02h / 2d.
Let y = x & (x-1):
(10 & 01) / (02h & 01h)
y equals 00.

The general example, as I already stated in my first post, is that any number ending with the last two bits 10 invalidates the claim, since the result of the expression is that BOTH the last two bits are reset.

As you know, it is sufficient to produce one contradictory example in order to invalidate any rule.

Have a nice day.

First to be clear, Peter' claim was to clear the right-most 1 bit, not to be confused with clearing the LSB: (e.g. 0xABCD & 0xFFFE).

So in both of your examples, which you use binary numbers ending in 10b, the result is that the right-most 1 bit (e.g. the n-1 position) is indeed cleared resulting in 00b.

So what's the problem? The original number x ending in 10b already had 0 as its LSB before the operation and post operation it's still 0. The only thing that changes was the right most 1 bit which was in the n-1 position.

This is not a counter-example. Rather, you've just given more examples to support the operation.

Count the number of bits set -

int count_set_bits( int n )
{
int count = 0;
while ( n ) {
++count;
n &= (n-1);
}
return count;
}

The loop runs only as many times as there are bits set in n.

John Doe is great :)))

Great post! I've been looking for some material to study bitwise operators and the operations that are possible. I'm probably going to buy that book since I though it is quite a must read!

Keep up the great work!

Dude, John Doe, seriously -- relax, bro. Remember your manners.

John Doe:

Both of your examples produce correct results with the algorithms presented in the article. For 0x42:

```0x42:             0b101010
0x42 & (0x42 -1): 0b101000
```

So, the rightmost 1 bit has been cleared. Same for 0x2:

```0x2:           : 0b10
0x2 & (0x2 - 1): 0b00
```

In both cases, the rightmost (ie, LSB) 1 bit has been set to 0, which is the correct behaviour.

As you say:

since the result of the expression is that BOTH the last two bits are reset.

But the last bit wasn't set in the input number, so it hasn't been cleared, it was 0 to start with. The algorithm's purpose is to clear the rightmost 1 bit.

I collected dec2bin() functions from several languages and stored them here:

John Doe, I am still not sure what you mean. It does what it says - turns off the rightmost 1-bit. It does not modify other bits.

Andrew, thanks for collection but I see several problems with Python's solution and Perl's solution.

As I wrote in an earlier comment bin() is a feature of Python 2.6 and bin(-x) is just -bin(x) that does not show the representation of negative numbers.

The problem with Perl's is that it shows too many bits 1-bits for negative numbers and you want to limit that. On a 64 bit machine -1 gets printed as 11111111111111111111111111111111111111111111111111111111111111.

A bit shorter:

```void int_to_bin(int num) {
int i;
for (i=7; i>=0; i--)
printf("%i", (num&(1<<i)?1:0));
printf("\n");
}
```

Kindly give the source of your hacks like this site

http://graphics.stanford.edu/~seander/bithacks.html

which has all that you are saying since 2005 !!!

Like he said in the intro, these things are second nature to embedded systems programmers. That implies that they are empirical knowledge (albeit only within a specific group of people.) Empirical knowledge does not require citation.

Peter, I don't know how you have the nerve to read some unintelligent rude people flaming. Great article! I admire your skills.

For the bonus stuff, not sure, but maybe the python solution should print the string reversed? like:
print r[::-1]

Good luck to you!

ps: yes, getting into google is tough, but maybe I'll try again :)

You must be doing something *right* PK, as you've got some peoples' panties in a twist.

Let's not forget you're self-taught, and you present your articles to a wide audience, in an accessible writing style.
We might not have known about some of the excellent examples and references in the comments had you not taken the time to write and publish your article.

Good on ya.

('Hack' was coined in the 1950's at MIT. If 'hack' has a bad connotation today, borne out of fear by the technology illiterate, then it only means some people are not aware of history. History requires no technical skill to learn. We don't need to eliminate this word, we need to eliminate ignorance and fear.)

> Bit Hack #6. Turn off the rightmost 1-bit
This can be used to test if the number is a power of 2 (or zero):

if((x & (x-1)) == 0) // x is a power of 2

You should read bithacks page and Hacker's Delight book by Henry Warren, Jr. Both contain a lot of more complex bit tricks.

You mixed up C language Right and Left shifts at the top of the page

Passer by: Thanks for noticing. I fixed the mistake.

IMHO, it's better if you don't set things on the macros unless it's necessary. It makes code more readable and allows composing the macros. For example the "rightmost off" one, as Peter Kankowski said, can be composed to make a power of 2 test.

B_TURNOFF_1(n); /* Did n change? */

#define RIGHTMOST_OFF(x) ((x) & ((x)-1))
#define IS_POW2(x) (RIGHTMOST_OFF(x)==0)

i = RIGTMOST_OFF(i); /* More readable */
if (IS_POW_2(j)) {
/* do something */
}

My \$.02

The first few are pretty common and I don't bat an eye when I see them in real C code. But the rest... wow. You, sir, have outdone yourself with bit hackery!

I just stumbled on this today. Even though the original posts were a year ago, I thought I'd clarify that it looks like John Doe was expecting the hack to be: x & ~1 (e.g. specifically unsetting the lowest-order bit). I'm pretty sure he missed the goal being to unset the lowest order _set_ bit.

And also here how to swap two vars without a temp var using bit wise operations:

i will write it in C
void Swap_Integers(int *x,int *y)
{
*x = *x ^ *y;
*y = *x ^ *y;
*x = *x ^ *y;
}

that is it and yeah it is obvious a little but here how it goes it depend on the concept that two XOR operations on the same var can be cancelled f.e. a ^ b ^ b = a
so first i put the XOR of both in x (x = x^y) now then to put x in y you just need another XOR with x (y = x ^ y ^y) and after that x will equal ( x ^ the new y (holding x inside) to be y ^ x ^x ) have fun and you can use this concept to make encryption also and i will leave that as an exercise to you ;) by the way nice work my friend peter

Two minor things I've used a few times on my Atari ST, when I needed to count through a mask, leaving some bits as they were:
-This is a simple version:

Count up:

```  count = ((count | ~mask) + 1) & mask;
```

Count down:

```  count = ((count - 1) & mask);
```

You may find it useful for microcontrollers and output ports (welll... actually also mixed ports where some of the pins are inputs).

Sherif - Your 'exchange' is great. I'd prefer using it directly without function call, to eliminate the pointer stuff and the overhead of call/ret.
Someone once said to me: "you can't write a CRC calculation routine in C without a temp variable". The exchange above would make it possible.

I've used something similar...

```c = *s++;
if(13 == c ||Â 10 == c)  // if end of line
{
if((c ^ 13 ^ 10) == s[0]) // if oposite character is following; eg CR/LF or LF/CR
{
s++; // skip that char
}
}
```

To convert a digit to a binary number:

```if('1' == (c | 1)){ digit = c & 1; }
```

octal...

```if('7' == (c | 7)){ digit = c & 7 }
```

Oh, and instead of doing for instance...

```swich_is_on = (PORTA & (1 << PA3)) ? 1 : 0;
```

Why not use..

```switch_is_on = (PORTA >> PA3) & 1;
```

To detect a carry, when you don't have the carry bit available:

```uint8_t a;
uint8_t b;
uint8_t prev_a;
a = (any value);
b = (any value);

prev_a = a;
a = a + b;
carry = a < prev_a;
```

This works because b can be max. 255. A can be max. 255. (255+255) & 255 = 254, which is smaller than the previous value.

Same thing for subtracting; just check for a > prev_a than, instead of a < prev_a.

Does the odd-even trick matter?

Because if you're doing the usual x%2 to check for even/oddness, your machine will do a >> operation since your mod is a power of two. This takes one cycle, just like your bit hack.

Why should we rely on compiler optimization? If I see x%2 instead of (x&1) I feel like something written by a non-professional.

I'm a web developer in PHP and JavaScript and only recently have I become interested in bitwise operations. I don't really have a need for them, but I'd like to know more about them. #1 I can see a use-case for - of course I sometimes want to know if integers are odd or even - but the rest of them I can't see why you would ever want/need to do this.

Can someone please provide some examples of why you would want to do things to the nth bit? I don't see what this actually achieves.

How about making an amber and green LED alternately flash on your cool new widget you are building with a microcontroller?
Testing so a robotic control program will know that one of its sensors has tripped. (it has hit the wall, and maybe should reverse for a bit.)
This type of activity is usually reserved for hardware programming / embedded systems. It's what makes your keyboard work with a single chip and an embedded program to convert switch closures into a stream of characters the computer can use as input.

Thanks Mark. So I'm relatively safe in my ignorance of these then - until I start trying to install Linux on my toaster.

A binary word is not just a number. It is also a set: for each possible element value, a 1 tells you it is present, a 0 it is not. A byte can represent days of a week, a 32-bit word is enough for a month. 0x6060c183, shifted and masked, identifies the weekend days in any month.

In C++ std::bitset<> wraps a lot of this stuff in less hacky garb.

Perhaps the title was just trying to grab ones eye, but I don't think you must absolutely know any of these. I'd just use a library that has a method to do all of these things.

For example: NumberUtils.isEven(...) is better than the bit hack because it's:
2) More tested
3) More distributable since it's already a library
4) Less work because I didn't have to write/think of it

I did find the article to be very interesting though. Thanks

great post. Is there a way to find the number of set bits in an integer using bit hacks?

Here's bit twiddling in Python: http://www.finalcog.com/bit-twiddling-python

Thanks

can you please make it in printable form so i can read it on the journey home.

congratulations nice paper, but so , i wrote about this in last yeah, in portuguese language , look this http://coolerlab.wordpress.com/2011/11/24/a-magia-dos-bits/ around of same issue that i wrote...

I haven't read "Hacker's Delight", but all (non-obvious) tricks in you article are mentioned here.

Unfortunately, some of them, like
``` min = y ^ ((x ^ y) & -(x < y)); max = x ^ ((x ^ y) & -(x < y)); abs = (x ^ (x >> 31)) - (x >> 31) // For 32-bit signed int```

seem to be less efficient than obvious:
``` min = x < y ? x: y; max = x < y ? y: x; abs = x < 0 ? -x: x;```

how to toggle the odd and even bits ?

x ^= 1

how to toggle the odd bits and the even bits of a given number.

I just read your bash articles and thought, these could easily be converted into bash using (( )) syntax around the bitwise tests. Input data as such: 2#0010,1011 or 43.
As far as printf:
if input is decimal and you want to see binary use:
pos: "\$(echo "obase=2; ibase=10; x" | bc)"
neg: "\$(echo "obase=2; ibase=10; \$((2**wordSize - x))" | bc)"
if input is binary and you want to see decimal use:
pos: "\$(echo "obase=10; ibase=2; \$x" | bc)"
neg: \$(( ~0xff | 2#\$x ))
I wouldn't call your article hacks, these are standard practices, especially for assembler programming.

Great tutorial, but I wish he'd given some context for these. The even/odd is a well-known one, but propagation of rightmost 1-bit? I have no idea what that, or most of these, are used for.

You might enjoy reading the HAKMEM also.

Awesome stuff!

On the very first one it has "if ((x & 1) == 0) {" Instead of doing the compare to 0 you need to let the following code be run second because all you need to do is and x and 1. if it is zero that would be false and it falls through and runs the code you have moved to the bottem. If it is not zero you move the code from the else up and run it.

That depends on the language used. Not all languages interpret 0 as false. I was going to comment that the second example did not use "== 0", but assumed 0 evaluated to false, but not in C#.

The most simple way to check for nâ€™s divisibility by 9 is to do n%9.
Another method is to sum the digits of n. If sum of digits is multiple of 9, then n is multiple of 9.
The above methods are not bitwise operators based methods and require use of â€˜%â€™ and â€˜/â€™. The bitwise operators are generally faster than modulo and division operators. Following is a bitwise operator based method to check divisibility by 9..

you can check this also with the example :-

http://www.firmcodes.com/check-number-multiple-9-using-bitwise-operators/

It is an error to assume that arithmetic in C is 2's complement. It may be, it may be some of the time depending on optimizations done by the compiler. It is not part of the language specification, the compiler is free to do as it chooses. It is part of a larger problem with C where there is a twilight zone of undefined behavior. The Linux core is written correctly according to the C specifications. Most other C code is not, including common Linux tools. It is a simple language, people assume they know it well because they have years of hands on experience. It is an old language with assumptions from the 1970's. If you fail to read and obey the actual specifications which are rather restrictive your code will exhibit undefined behavior with no warnings from the compiler.

In C++2020, all integer types will be guaranteed to be two's complement.

Just as one example, the compiler can assume that the carry flag is clear after an unsigned addition and go and do some optimizations based on that. If you have just done a 2's complement addition the carry flag could be set leading to undefined behavior.

Eagerly waiting for your next writings..
Thanks a lot..

Hey, nice work man I also created an article about some tricks you didn't mention. I would appreciate if you check it out it's really interesting :)

http://softwarebehindscenes.blogspot.sk/2016/05/dirty-bitwise-tricks-each-programmer.html

-43 has 7th bit set, still when i run the program, it says not set

Sorry my bad, the problem is resolved

Still looking for efficient ways to:
1. Count how many bits set to 1
2. Find the left-most 1.

I recently learned this clever test for whether x is a power of 2:
(x & (x-1))==0

About counting 1-bits. The artical shows how to clear rightmost 1-bit. This way you do a loop untill you get zero:
`int count = 0; while(x!-=0) {count++; x&=x-1;}`

You use the POPCNT instruction. Compilers have an intrinsic, __popcount(i). In C++, std::bitset

<32>

(i).count() compiles to a single POPCNT instruction.

An old Binary HAck from Andy Hetzfeld the Original MacDeveloper is using 3 XOR writes to switch memory locations WITH NO TEMPORARY VARIABLE. This hack has been immortalized
https://en.wikipedia.org/wiki/XOR_swap_algorithm

Thanks for the fine article

Hello i think your int to bin function is mislabeled it prints a char not a int. This is my suggestion for how to convert an int to bin while retaining old functionality.

void char_to_bin(char num) {
char str[9] = {0};
int i;
for (i=7; i>=0; i--) {
str[i] = (num&1)?'1':'0';
num >>= 1;
}
printf("%s ", str);
}

void int_to_bin(int num){
int i;
for(i=sizeof(int)-1;i>=0;--i){
char_to_bin(((char*)&num)[i]);
}
printf("\n");
}