Bit Hacks

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 operations (such as counting the number of 1 bits in an integer) by looping over individual bits, these programming tricks 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

Numbers in this 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 most significant bit (or in signed arithmetic - sign 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 like this topic, you can subscribe to my blog, or you can just read along. There is also going to be the second part of this article where I'll cover more advanced bit hacks, and I'll also release a cheat sheet with all these bit tricks.

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:

&   00000001   (note: 1 is the same as 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.

&   00000001

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.

&   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)

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)

What about -120 and 6th bit?

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

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

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:

^   00100000

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

^   00100000

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)

    01011000    (x)
&   01010111    (x-1)

    10000000    (x = -128)
&   01111111    (x-1 = 127 (with overflow))

    11111111    (x = all bits 1)
&   11111110    (x-1)

    00000000    (x = no rightmost 1-bits)
&   11111111    (x-1)

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)

    01110000  (x)
&   10010000  (-x)

    00000001  (x)
&   11111111  (-x)

    10000000  (x = -128)
&   10000000  (-x = -128)

    11111111  (x = all bits one)
&   00000001  (-x)

    00000000  (x = all bits 0, no rightmost 1-bit)
&   00000000  (-x)

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)

    01110111  (x)
|   01110110  (x-1)

    00000001  (x)
|   00000000  (x-1)

    10000000  (x = -128)
|   01111111  (x-1 = 127)

    11111111  (x = -1)
|   11111110  (x-1 = -2)

    00000000  (x)
|   11111111  (x-1)

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)

    01110111  (x)
    10001000  (~x)
&   01111000  (x+1)

    00000001  (x)
    11111110  (~x)
&   00000010  (x+1)

    10000000  (x = -128)
    01111111  (~x)
&   10000001  (x+1)

    11111111  (x = no rightmost 0-bit)
    00000000  (~x)
&   00000000  (x+1)

    00000000  (x)
    11111111  (~x)
&   00000001  (x+1)

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)

    01110111  (x)
|   01111000  (x+1)

    00000001  (x)
|   00000010  (x+1)

    10000000  (x = -128)
|   10000001  (x+1)

    11111111  (x = no rightmost 0-bit)
|   00000000  (x+1)

    00000000  (x)
|   00000001  (x+1)

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

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

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 like this topic you to subscribe to my blog. See you next time!

Another Bonus

There's a book entirely about bit hacks like these. It's called "Hacker's Delight". You'll love it, if you are into this stuff.


June 30, 2009, 20:18

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 :)

Bolutife Ogunsola Permalink
October 22, 2010, 12:52

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 :-)

Mickey Permalink
July 24, 2012, 14:34

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

Sushil Permalink
July 21, 2018, 16:06

Suggest extending to hex instead.
BTW, "10100b = 101b x 100b = 5 x 8 = 40" should be "5x2 =20".

Matt Permalink
June 30, 2009, 20:18

Your python code has an error

while b:

should be

while bits:
Justin Thyme Permalink
June 30, 2009, 20:23

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.

Daniel Swe Permalink
August 18, 2011, 18:20

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.

nick Permalink
September 25, 2015, 01:26

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

Peter A. Permalink
December 20, 2015, 22:13

Bit fiddling.

Sam Shipman Permalink
May 11, 2018, 18:47

The authors of HAKMEM would like a word with you.

Jordan Permalink
May 12, 2018, 03:51

George Boole would like a word with authors of HAKMEM.

June 30, 2009, 20:46

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

bolke Permalink
May 23, 2012, 12:52


June 30, 2009, 21:10

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!

June 30, 2009, 21:13

Please also check this out for lot of bit hacks:

June 30, 2009, 21:55

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.


July 01, 2009, 00:51

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

July 01, 2009, 03:09

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.

January 08, 2017, 00:09

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

Firefly Permalink
July 01, 2009, 03:49

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

July 01, 2009, 09:14

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?

July 01, 2009, 12:26

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

July 01, 2009, 12:53

Nice post!

Printing binary numbers in python is quite straight-forward:

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

July 01, 2009, 13:13

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

July 01, 2009, 13:36

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).

July 01, 2009, 13:37

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

July 01, 2009, 13:39

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

July 01, 2009, 13:53

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

anonym Permalink
April 19, 2011, 12:38

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

Partho Permalink
February 25, 2012, 03:48

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

William Swartzendruber Permalink
June 13, 2014, 20:55

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

anon Permalink
April 18, 2016, 05:39

try it when a == b :)

January 08, 2017, 00:19

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

John Doe Permalink
July 01, 2009, 15:06

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.


Bill Permalink
October 20, 2010, 14:28

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

y = x & 0xFFFFFFE

(at least for 32-bit values)

Tom Kha Gai Permalink
October 20, 2010, 16:36

I do not see any problem.

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

jsc42 Permalink
October 21, 2010, 12:52

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.

January 08, 2017, 00:23

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

John C. Permalink
October 21, 2010, 12:54

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.

Eralp Permalink
March 11, 2014, 21:31

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.

January 08, 2017, 00:24

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

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

August 05, 2015, 09:13

Right, turning off the rightmost bit is this

x = n & (~1)

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

January 08, 2017, 00:25

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

January 08, 2017, 00:22

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

John Doe Permalink
July 01, 2009, 15:11

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?

vaibhav Permalink
October 20, 2010, 22:34

Very useful in this data structure:

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

July 01, 2009, 15:17

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

July 01, 2009, 15:48

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.

Billy Vandory Permalink
April 02, 2014, 16:38

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

anon Permalink
May 21, 2015, 22:14

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

July 01, 2009, 15:58

check if a number is power of 2

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

Tom Kha Gai Permalink
October 20, 2010, 16:40

FIX: && => &

Additionally: can also be written as

(n & (-n)) == n

Why Permalink
July 01, 2009, 18:59

This is where I stopped reading your article:

>  -  bitwise shift left

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

Please use < to insert '
July 01, 2009, 19:37

Why: ok.

John Doe Permalink
July 02, 2009, 09:18

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.

JD2 Permalink
October 20, 2010, 18:59

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.

Kumar Permalink
July 02, 2009, 10:30

Count the number of bits set -

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

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

July 02, 2009, 10:47

John Doe is great :)))

Filipe La Ruina Permalink
July 02, 2009, 15:12

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!

Paul Doe Permalink
July 02, 2009, 19:15

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

Jeremy Permalink
July 02, 2009, 23:38

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.

July 03, 2009, 06:13

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

July 03, 2009, 17:16

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.

July 06, 2009, 19:32

A bit shorter:

void int_to_bin(int num) {
  int i;
  for (i=7; i>=0; i--)
    printf("%i", (num&(1<<i)?1:0));
Copy Cats Permalink
July 07, 2009, 10:57

Kindly give the source of your hacks like this site

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

He Doesn't Need A Source Permalink
October 20, 2010, 21:36

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.

Zornitsa Kostadinova Permalink
July 07, 2009, 17:01

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 :)

argv Permalink
July 30, 2009, 02:31

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.)

October 30, 2009, 01:16

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

Passer by Permalink
January 03, 2010, 23:38

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

January 04, 2010, 00:41

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

March 02, 2010, 19:11

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

April 02, 2010, 02:27

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!

Chris Permalink
April 20, 2010, 12:48

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.

Sherif Permalink
May 03, 2010, 15:15

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

July 31, 2010, 00:36

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; }


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.

cassandra Permalink
September 14, 2010, 21:20

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.

cyanide Permalink
January 18, 2017, 01:00

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.

Gregor Permalink
October 20, 2010, 18:13

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.

YA mark Permalink
October 21, 2010, 13:47

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.

Gregor Permalink
October 21, 2010, 20:46

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

Nathan Myers Permalink
May 11, 2018, 05:06

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.

October 21, 2010, 00:03

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:
1) More readable
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

October 21, 2010, 01:25

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

October 21, 2010, 06:39

Here's bit twiddling in Python:

Jeff Permalink
October 21, 2010, 11:55


brucebanner Permalink
October 21, 2010, 13:19

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

February 16, 2012, 17:27

congratulations nice paper, but so , i wrote about this in last yeah, in portuguese language , look this around of same issue that i wrote...

cyanide Permalink
January 18, 2017, 00:45

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;

Amith Kumar Permalink
July 14, 2013, 09:18

how to toggle the odd and even bits ?

cyanide Permalink
January 18, 2017, 00:49

x ^= 1

Amith Kumar Permalink
July 14, 2013, 09:18

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

December 16, 2013, 17:16

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.

Badspiegel Permalink
January 28, 2014, 11:44

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.

April 08, 2014, 16:37

You might enjoy reading the HAKMEM also.

Rishul Matta Permalink
May 29, 2014, 15:26

Awesome stuff!

nedwards Permalink
October 19, 2014, 05:36

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.

October 01, 2015, 12:14

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#.

vishal chovatiya Permalink
January 12, 2015, 06:27

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

Fraz Permalink
March 26, 2015, 16:02

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.

Nathan Myers Permalink
May 11, 2018, 05:09

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

Fraz Permalink
March 26, 2015, 16:09

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.

Protap Permalink
May 05, 2016, 13:54

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

ZyTr0n Permalink
May 31, 2016, 21:18

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 :)

Here's the link:

Abhijit Kale Permalink
September 14, 2016, 11:10

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

Abhijit Kale Permalink
September 14, 2016, 11:17

Sorry my bad, the problem is resolved

Phil Permalink
January 10, 2017, 20:51

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

cyanide Permalink
January 18, 2017, 00:19

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;}

Nathan Myers Permalink
May 11, 2018, 05:11

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


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

May 11, 2018, 21:50

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

Thanks for the fine article

Some name Permalink
September 05, 2018, 06:58

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;

December 28, 2018, 16:19

This post is nearly 10 years old and has been a great help in my work. Thank you, and thank you for all the useful comments.

Leave a new comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "unix_143": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.