Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Low Level Bit Hacks You Must Know

catonmat.net

Post reply on HN
Print view View original

1–10 of 49 posts

Re: Low Level Bit Hacks You Must Know

#2

Post by larsu »

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.

Re: Low Level Bit Hacks You Must Know

#4

Post by benhoyt »

TimMontague wrote: post #3

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

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.

Re: Low Level Bit Hacks You Must Know

#7

Post by CountHackulus »

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

Re: Low Level Bit Hacks You Must Know

#8

Post by dfox »

larsu wrote: post #2

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.

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.

Re: Low Level Bit Hacks You Must Know

#9

Post by mahmud »

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.

Post reply on HN