7 ms·

Low Level Bit Hacks You Must Know

158 points by jonpaul 16y ago

larsu 16y ago
Bit Hack #6. Turn off the rightmost 1-bit. Now it finally gets more interesting!!! Bit hacks #1 - #5 were kind of boring to be honest. Does anybody know a practical use case for that? I have personally never encountered a situation were I needed to manipulate the right most 1-bit. Otherwise it's a nice introduction to bit hacking.
- dfox 16y ago
  This is mainly useful for testing whenever given number is integral power of 2 (you gen zero in that case). Otherwise it might be useful for some special purpose counters/timers.
- barrkel 16y ago
  Let's say you use a bitmask for keeping track of free registers in a compiler. To "allocate" a register, you'll want to clear a bit, to indicate that the register is no longer free. That's the context I learned this trick in. It's used in the Embarcadero (ex-Borland) compilers (Delphi, C++, etc.).
- sliverstorm 16y ago
  Perhaps you are using a microcontroller with memory-mapped control registers?
- RiderOfGiraffes 16y ago
  If you're handed a bit mask of events or flags then it can be used to iterate through the bits that are set, rather than all the bits. while flags!=0: right_most = flags & (-flags) process(right_most) flags &= ~right_most
TimMontague 16y ago
Here's a much more comprehensive collection of bit hacks: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html
- benhoyt 16y ago
  Yeah, that's a better one, with more actual hacks. Most of the "hacks" in the original post weren't really hacks, but the way embedded programmers set and toggle bits every day.
- alextgordon 16y ago
  It depresses me that something as simple as int mask = v >> sizeof(int) * CHAR_BIT - 1; unsigned int r = (v ^ mask) - mask; can be granted a patent (http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs http://graphics.stanford.edu/~seander/bithacks.html#IntegerA...).
  - yason 16y ago
    Granted, yes. There was discussion about whether the patent is at all valid, given abundant prior art. However, it depresses me too because you probably need lots of money and possibly a lawsuit to settle out the validity issue.
- IgorPartola 16y ago
  Ha. Next time someone asks how to swap two values at an interview question (I think this is pretty common): #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
  - cs_loser 16y ago
    Is it pretty common? As someone who does a fair number of software engineer interviews, that's a trick question. The real answer to "swap two vars with no temps" is: 1. Don't be clever in our code base. Use a temp variable. 2. There's various dumb tricks with XOR, and possibly add/subtract if overflows don't break. 3. A sequence of several instructions where each of them requires the result of the previous one may not execute particularly fast on modern processors. Instruction/cycle counts -- like 3 -- are great when there's no pipeline and no cache, but otherwise pretty much useless. 4. The things you're swapping might be local variables, and when the compiler has -O <anything> specified, local variables start getting weird, and "swap" can sometimes be done in zero instructions, namely by the compiler noting that they have now been swapped and using the other one for the rest of the basic block. (or further dominated basic blocks for that matter) 5. If the things you're swapping are in main memory, or even if it's not in L1, you're going to be incurring a cost much greater than the temporary use of a register. (and, if you don't know where they are and it might be main memory, this might dominate the average runtime) The answer is definitely not "three xors".
darwinGod 16y ago
And, Here's a draft of Bitwise Tricks and Techniques, by Knuth. http://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz http://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz
golgo13 16y ago
Also works in SQL Server: http://msdn.microsoft.com/en-us/library/ms176122.aspx http://msdn.microsoft.com/en-us/library/ms176122.aspx Sweet!
CountHackulus 16y ago
If you're interested in reading about more of these, and how they work I'd highly suggest reading the book Hacker's Delight by Henry S. Warren[1]. I know that I've used more than a few of the tricks in my day-to-day work. [1] http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ref=sr_1_1?ie=UTF8&s=books&qid=1287586055&sr=1-1 http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201...
- swaits 16y ago
  Indeed, a great book. It's also mentioned in the article.
mahmud 16y ago
Here is a fun challenge for language snobs: implement bit-streams for your favorite language. Here is a simple signature: bitvec read_nbits (unsigned int count, bitstream input); bool write_nbits (unsigned int count,bitvec bits, bitstream output); Then add a multirecord I/O. That is, read a record of bitvecs, each N bits wide, where the length is not given but encoded in the bitstream in this manner: read a bitvec record of N bits, if the high-bit is set (take it in whatever endian you like), read another record and repeat, if the high bit is not set, return whatever you read thus far. Then add the ability to return the bitvec records as single integers (bignums even) both signed and unsigned, taking them in this manner. If the bitvecs are unsigned, each record contributes its 7 least significant bits, and the high bit is dropped. Taking the bit on either end of the first record as the most signficant, iterate over the rest and shift and OR according to your endian needs to construct an integer from the sum of all the bits. When I first did this exercise, I was very close to gouging my own eye-balls out, but after I did it, I started to think of bits as something very natural, and not to be feared.
- pepsi_can 16y ago
  You wouldn't happen to still have your code? This sounds like an interesting exercise. Maybe you could blog about your implementation and we can compare notes.
  - mahmud 16y ago
    The source is in my old thinkpad, but would love to redo it in my new favorite language, AliceML :-) http://www.ps.uni-saarland.de/alice/ http://www.ps.uni-saarland.de/alice/
- fleitz 16y ago
  let nthbit (bitContainer:'T) nth : bool = (bitContainer &&& ((1 :> 'T) <<<nth)) let bitstream (bitContainerSeq:seq<'T>) : seq<bool> = let sz = sizeof<'T> bitContainerSeq |> Seq.map (fun b -> [0..sz] |> nthbit b |> Seq.ofArray ) |> Seq.concat I think that should do it unfortunatley I'm away from an F# compiler
Dilpil 16y ago
Is working on embedded systems really this fun? I might have to change careers...
- bryanlarsen 16y ago
  It was 10-20 years ago. The funnest project I ever worked on was to implement a 17-function motor controller with 40-bit precision onto an MCU with 2K of RAM and 64 BYTES of RAM. That was in '93. Today embedded systems generally run Linux. You get to write a bit of assembly language code in your bootloader, and then it's just bog standard Unix programming. It's even likely that you'll be doing most of your coding in a scripting language, although it's more likely to be Lua than Ruby...
  - oiuytgfrtgyhuji 16y ago
    There are still a lot of 8051s and MSP430s out there. The fun thing about embedded is that since everything is done as a result of interrupts or clock signals it's all the joys of multitasking without a threading library. I just got handed a project where the 'app' was just main() { while(1) {} } ! Everything happens as the result of functions that get magically called when certain bit patterns appear
    - mahmud 16y ago
      Look into Esterel for some theoretical grounding. It will help you reason about reactive systems.
  - mentat 16y ago
    It's my impression that this sort of "fun" work is still done in firmware engineering at Broadcom for instance.
- muon 16y ago
  It is and it will be for the long time to come. Bit twiddling has important role in device drivers, firmware etc.
js2 16y ago
Previous submission http://news.ycombinator.com/item?id=681282 http://news.ycombinator.com/item?id=681282
bhavin 16y ago
As much as I love bit manipulation, I have to say that most (not all) of them don't provide any real performance gain for C/C++ code (only some geeky satisfaction of writing difficult to interpret code!).. e.g. with any decent compiler... * if ((x & 1) == 0) performs same as, if ((x % 2) == 0) * if (x & (1<<n)) same as, if (x% (pow(2,n))) so on.. on the other hand, i find bit operations really handy when the variables in question are to be treated as separate bits than normal base-10..
- deleted 16y ago
  [deleted]
- alexgartrell 16y ago
  x & (1<<n) is not the same as (x % pow(2, n)) Take x = 2 and n = 1 x & (1 << n) = 0b10 & 0b10 = 0b10 x % pow(2, n) = 2 % 2 = 0 = 0b0 0b0 /= 0b10 fwiw, you were actually looking for (x & ((1 << n) - 1)) = (x % pow(2, n)) That aside, you're absolutely right. Using bit ops is almost always a bad idea. It turns a simple store (to a byte-addressed memory address) into a read, manipulate, and store (to a bit within a byte-addressed memory address) which can have pretty bad side affects in any concurrent environment.
- wingo 16y ago
  Agreed regarding modulo, but `pow' returns a floating-point number.
  - bhavin 16y ago
    sorry, what i meant there wasn't literally pow function per se, but a function which does the job..
grobolom 16y ago
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.
newgrad 16y ago
oo~ number 7 is interesting
yason 16y ago
These aren't hacks really: they're just basic operations in binary arithmetic that anyone who has seriously coded C or assembly must have bumped into, probably quite early. Other's have already mentioned but for real hacks in the unintuitive sense, check out Hacker's Delight and http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html.
nait 16y ago
Here are some more bit hack algorithms http://www.aggregate.org/MAGIC/ http://www.aggregate.org/MAGIC/ The intersection of tricks on all those sites is quite large but on every one of them there's something you haven't seen before. By the way if you like to wrap your mind around such tricks you might also find some gems here: http://www.azillionmonkeys.com/qed/asmexample.html http://www.azillionmonkeys.com/qed/asmexample.html
makmanalp 16y ago
If you like this stuff, you'll love the book "Hacker's Delight" which is just full of these: http://www.hackersdelight.org/ http://www.hackersdelight.org/

158 points by jonpaul 16y ago

larsu 16y ago

Bit Hack #6. Turn off the rightmost 1-bit. Now it finally gets more interesting!!! Bit hacks #1 - #5 were kind of boring to be honest. Does anybody know a practical use case for that? I have personally never encountered a situation were I needed to manipulate the right most 1-bit. Otherwise it's a nice introduction to bit hacking.

dfox 16y ago
This is mainly useful for testing whenever given number is integral power of 2 (you gen zero in that case). Otherwise it might be useful for some special purpose counters/timers.
barrkel 16y ago
Let's say you use a bitmask for keeping track of free registers in a compiler. To "allocate" a register, you'll want to clear a bit, to indicate that the register is no longer free. That's the context I learned this trick in. It's used in the Embarcadero (ex-Borland) compilers (Delphi, C++, etc.).
sliverstorm 16y ago
Perhaps you are using a microcontroller with memory-mapped control registers?
RiderOfGiraffes 16y ago
If you're handed a bit mask of events or flags then it can be used to iterate through the bits that are set, rather than all the bits. while flags!=0: right_most = flags & (-flags) process(right_most) flags &= ~right_most

TimMontague 16y ago

Here's a much more comprehensive collection of bit hacks: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html

benhoyt 16y ago
Yeah, that's a better one, with more actual hacks. Most of the "hacks" in the original post weren't really hacks, but the way embedded programmers set and toggle bits every day.
alextgordon 16y ago
It depresses me that something as simple as int mask = v >> sizeof(int) * CHAR_BIT - 1; unsigned int r = (v ^ mask) - mask; can be granted a patent (http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs http://graphics.stanford.edu/~seander/bithacks.html#IntegerA...).
- yason 16y ago
  Granted, yes. There was discussion about whether the patent is at all valid, given abundant prior art. However, it depresses me too because you probably need lots of money and possibly a lawsuit to settle out the validity issue.
IgorPartola 16y ago
Ha. Next time someone asks how to swap two values at an interview question (I think this is pretty common): #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
- cs_loser 16y ago
  Is it pretty common? As someone who does a fair number of software engineer interviews, that's a trick question. The real answer to "swap two vars with no temps" is: 1. Don't be clever in our code base. Use a temp variable. 2. There's various dumb tricks with XOR, and possibly add/subtract if overflows don't break. 3. A sequence of several instructions where each of them requires the result of the previous one may not execute particularly fast on modern processors. Instruction/cycle counts -- like 3 -- are great when there's no pipeline and no cache, but otherwise pretty much useless. 4. The things you're swapping might be local variables, and when the compiler has -O <anything> specified, local variables start getting weird, and "swap" can sometimes be done in zero instructions, namely by the compiler noting that they have now been swapped and using the other one for the rest of the basic block. (or further dominated basic blocks for that matter) 5. If the things you're swapping are in main memory, or even if it's not in L1, you're going to be incurring a cost much greater than the temporary use of a register. (and, if you don't know where they are and it might be main memory, this might dominate the average runtime) The answer is definitely not "three xors".

darwinGod 16y ago

And, Here's a draft of Bitwise Tricks and Techniques, by Knuth. http://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz http://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz

golgo13 16y ago

Also works in SQL Server: http://msdn.microsoft.com/en-us/library/ms176122.aspx http://msdn.microsoft.com/en-us/library/ms176122.aspx Sweet!

CountHackulus 16y ago

If you're interested in reading about more of these, and how they work I'd highly suggest reading the book Hacker's Delight by Henry S. Warren[1]. I know that I've used more than a few of the tricks in my day-to-day work. [1] http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ref=sr_1_1?ie=UTF8&s=books&qid=1287586055&sr=1-1 http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201...

swaits 16y ago
Indeed, a great book. It's also mentioned in the article.

mahmud 16y ago

Here is a fun challenge for language snobs: implement bit-streams for your favorite language. Here is a simple signature: bitvec read_nbits (unsigned int count, bitstream input); bool write_nbits (unsigned int count,bitvec bits, bitstream output); Then add a multirecord I/O. That is, read a record of bitvecs, each N bits wide, where the length is not given but encoded in the bitstream in this manner: read a bitvec record of N bits, if the high-bit is set (take it in whatever endian you like), read another record and repeat, if the high bit is not set, return whatever you read thus far. Then add the ability to return the bitvec records as single integers (bignums even) both signed and unsigned, taking them in this manner. If the bitvecs are unsigned, each record contributes its 7 least significant bits, and the high bit is dropped. Taking the bit on either end of the first record as the most signficant, iterate over the rest and shift and OR according to your endian needs to construct an integer from the sum of all the bits. When I first did this exercise, I was very close to gouging my own eye-balls out, but after I did it, I started to think of bits as something very natural, and not to be feared.

pepsi_can 16y ago
You wouldn't happen to still have your code? This sounds like an interesting exercise. Maybe you could blog about your implementation and we can compare notes.
- mahmud 16y ago
  The source is in my old thinkpad, but would love to redo it in my new favorite language, AliceML :-) http://www.ps.uni-saarland.de/alice/ http://www.ps.uni-saarland.de/alice/
fleitz 16y ago
let nthbit (bitContainer:'T) nth : bool = (bitContainer &&& ((1 :> 'T) <<<nth)) let bitstream (bitContainerSeq:seq<'T>) : seq<bool> = let sz = sizeof<'T> bitContainerSeq |> Seq.map (fun b -> [0..sz] |> nthbit b |> Seq.ofArray ) |> Seq.concat I think that should do it unfortunatley I'm away from an F# compiler

Dilpil 16y ago

Is working on embedded systems really this fun? I might have to change careers...

bryanlarsen 16y ago
It was 10-20 years ago. The funnest project I ever worked on was to implement a 17-function motor controller with 40-bit precision onto an MCU with 2K of RAM and 64 BYTES of RAM. That was in '93. Today embedded systems generally run Linux. You get to write a bit of assembly language code in your bootloader, and then it's just bog standard Unix programming. It's even likely that you'll be doing most of your coding in a scripting language, although it's more likely to be Lua than Ruby...
- oiuytgfrtgyhuji 16y ago
  There are still a lot of 8051s and MSP430s out there. The fun thing about embedded is that since everything is done as a result of interrupts or clock signals it's all the joys of multitasking without a threading library. I just got handed a project where the 'app' was just main() { while(1) {} } ! Everything happens as the result of functions that get magically called when certain bit patterns appear
  - mahmud 16y ago
    Look into Esterel for some theoretical grounding. It will help you reason about reactive systems.
- mentat 16y ago
  It's my impression that this sort of "fun" work is still done in firmware engineering at Broadcom for instance.
muon 16y ago
It is and it will be for the long time to come. Bit twiddling has important role in device drivers, firmware etc.

js2 16y ago

Previous submission http://news.ycombinator.com/item?id=681282 http://news.ycombinator.com/item?id=681282

bhavin 16y ago

As much as I love bit manipulation, I have to say that most (not all) of them don't provide any real performance gain for C/C++ code (only some geeky satisfaction of writing difficult to interpret code!).. e.g. with any decent compiler... * if ((x & 1) == 0) performs same as, if ((x % 2) == 0) * if (x & (1<<n)) same as, if (x% (pow(2,n))) so on.. on the other hand, i find bit operations really handy when the variables in question are to be treated as separate bits than normal base-10..

deleted 16y ago
[deleted]
alexgartrell 16y ago
x & (1<<n) is not the same as (x % pow(2, n)) Take x = 2 and n = 1 x & (1 << n) = 0b10 & 0b10 = 0b10 x % pow(2, n) = 2 % 2 = 0 = 0b0 0b0 /= 0b10 fwiw, you were actually looking for (x & ((1 << n) - 1)) = (x % pow(2, n)) That aside, you're absolutely right. Using bit ops is almost always a bad idea. It turns a simple store (to a byte-addressed memory address) into a read, manipulate, and store (to a bit within a byte-addressed memory address) which can have pretty bad side affects in any concurrent environment.
wingo 16y ago
Agreed regarding modulo, but `pow' returns a floating-point number.
- bhavin 16y ago
  sorry, what i meant there wasn't literally pow function per se, but a function which does the job..

grobolom 16y ago

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.

newgrad 16y ago

oo~ number 7 is interesting

yason 16y ago

These aren't hacks really: they're just basic operations in binary arithmetic that anyone who has seriously coded C or assembly must have bumped into, probably quite early. Other's have already mentioned but for real hacks in the unintuitive sense, check out Hacker's Delight and http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html.

nait 16y ago

Here are some more bit hack algorithms http://www.aggregate.org/MAGIC/ http://www.aggregate.org/MAGIC/ The intersection of tricks on all those sites is quite large but on every one of them there's something you haven't seen before. By the way if you like to wrap your mind around such tricks you might also find some gems here: http://www.azillionmonkeys.com/qed/asmexample.html http://www.azillionmonkeys.com/qed/asmexample.html

makmanalp 16y ago

If you like this stuff, you'll love the book "Hacker's Delight" which is just full of these: http://www.hackersdelight.org/ http://www.hackersdelight.org/