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

This article was brought to you by Online programming help service.

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:

Comments

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)

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.

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

no

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:
http://graphics.stanford.edu/~seander/bithacks.html

June 30, 2009, 21:55

Thanks for the article Peteris.

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

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.

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

a^=b;b^=a;a^=b;
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.

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.

Sorry.

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.

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.

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:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

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.

July 01, 2009, 15:58

check if a number is power of 2

if ( ( n && ( n-1 ) ) == 0 )
{
//power of 2
}
else
{
//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 '
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, Peteris' 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 ) {
++count;
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:

http://downloads.yellosoft.us/bin.txt

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));
  printf("\n");
}
Copy Cats Permalink
July 07, 2009, 10:57

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

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

Peteris, 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 peteris

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

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.

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.

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.

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: http://www.finalcog.com/bit-twiddling-python

Jeff Permalink
October 21, 2010, 11:55

Thanks

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 http://coolerlab.wordpress.com/2011/11/24/a-magia-dos-bits/ around of same issue that i wrote...

Amith Kumar Permalink
July 14, 2013, 09:18

how to toggle the odd and even bits ?

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.

March 11, 2014, 09:06

Excellent stuff!

March 11, 2014, 09:06

Excellent stuff!

April 08, 2014, 16:37

You might enjoy reading the HAKMEM also.

May 08, 2014, 02:20

Thanks for sharing!

Rishul Matta Permalink
May 29, 2014, 15:26

Awesome stuff!

Jerry Permalink
September 19, 2014, 14:24

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, It bit confusing while I making a try both same would end up with 1 some times. Any Idea ?

Tim @ Vinity Soft a best fleet software

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 28, 2014, 14:34

It's nice to come on your website. This is really helpful as well as interesting information here. Thanks for sharing this content through your portal. You are truly awesome.

Erika Permalink
December 08, 2014, 08:29

I was suggested this website by my cousin. I am not sure whether this post is written by him as nobody else know such detailed about my trouble. You are wonderful! Thanks!Nice blog here! Also your web site loads up fast! What web host are you using? Can I get your affiliate link to your host? I wish my website loaded up as quickly as yours lol
Christmas wallpaper thank you

December 14, 2014, 08:44

Thanks for clearing all my doubts in this low level bit hacks category. You have explained this topic very clearly!

Timmy Permalink
December 19, 2014, 11:11

Thank you for sharing the information on this specific topic along with your viewers. I personally, for just one appreciate how much work you went to in putting all this together. Thank you so very much. Asset Management Software at vinity soft inc.

Leave a new comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

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

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

Advertisements