Sign in to follow this  
fastcall22

C++ Interview Questions / leet bit-twiddling skillz

Recommended Posts

[url=http://www.gamedev.net/topic/612023-c-interview-questions/page__view__findpost__p__4869238]Original thread[/url]
I feel this discussion is worthy of a separate thread, as it does not particularly pertain to the discussion in the original thread.

[quote name='Hodgman' timestamp='1317789351' post='4869238']
No one broke out the leet bit-twiddling skillz? [img]http://public.gamedev.net/public/style_emoticons/default/biggrin.gif[/img]
[font="Courier New"][size="1"]count = (((((v - ((v >> 1) & 0x55555555)) & 0x33333333) + (((v - ((v >> 1) & 0x55555555)) >> 2) & 0x33333333)) + ((((v - ((v >> 1) & 0x55555555)) & 0x33333333) + (((v - ((v >> 1) & 0x55555555)) >> 2) & 0x33333333)) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;[/size][/font]
[/quote]

Okay, I need to know.

Here's my naive approach, in 20 operations (*):
[code]
unsigned count_bits( unsigned x ) {
x = ((x & 0x55555555) + ((x >> 1) & 0x55555555));
x = ((x & 0x33333333) + ((x >> 2) & 0x33333333));
x = ((x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F));
x = ((x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF));
x = ((x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF));
return x;
}
[/code]
Since a bit is, in itself, the number of bits in that bit, we can use 16 two-bit accumulators to count the number of bits are in each 2-bit group. This is done by selecting every other bit and adding it with it's neighbor. Then each pair of 2-bit accumulators are accumulated into 4-bit accumulators, and so on, until we get our result in the 16-bit accumulator.


Hodgman's sample code (taken from [url]http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive[/url]), however, reduces to 12 operations:
[code]
unsigned count_bits_reduced( unsigned x ) {
unsigned z = (x - ((x >> 1) & 0x55555555));
unsigned y = ((z & 0x33333333) + ((z >> 2) & 0x33333333));

return ((y + (y >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
[/code]
My questions are:
1) What advantages are gained by negating the value in: [font="Courier New"](x - ((x >> 1) &0x55555555)[/font]?
2) Why the multiplication of [font="Courier New"]0x1010101[/font], and the r-shift of 24?
3) Does this trickery scale to 64-bit integers? Or does it only apply to 32-bit integers?

[size="1"](*) Most likely not a very good base to make assumptions about speed, size, or performance[/size]

Share this post


Link to post
Share on other sites
N.B. I shamelessly stole the algorithm from [url="http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive"]this famous page[/url]. I take no credit for it's magic.[quote][The 12 operation method] is a hybrid between the purely parallel method above and the earlier methods using multiplies (in the section on counting bits with 64-bit instructions), though it doesn't use 64-bit instructions. The counts of bits set in the bytes is done in parallel, and the sum total of the bits set in the bytes is computed by multiplying by 0x1010101 and shifting right 24 bits.[/quote]

Share this post


Link to post
Share on other sites
[quote name='fastcall22' timestamp='1317795822' post='4869273']
1) What advantages are gained by negating the value in: [font="Courier New"](x - ((x >> 1) &0x55555555)[/font]?[/quote]
That's a clever way of computing the bit count of every 2-bit box. It's probably not better in practice than [code]x = ((x & 0x55555555) + ((x >> 1) & 0x55555555));[/code]

[quote]2) Why the multiplication of [font="Courier New"]0x1010101[/font], and the r-shift of 24?[/quote]
If you think of your 32-bit number as a 4-digit number in base 256, you are computing
[code] a b c d
* 1 1 1 1
-------
a b c d
a b c d
a b c d
a b c d
-------------
e f g h i j k[/code]
e, f and g are lost in overflow, so by shifting 24 places to the right, you recover h, and h = a + b + c + d. Notice that a, b, c and d are at most 8, so you won't have carry problems.

[quote]3) Does this trickery scale to 64-bit integers?[/quote]
Yes, and if you understand the 32-bit code, you should be able to write the 64-bit version yourself.

Share this post


Link to post
Share on other sites
Hrrmm drr hrrm, forgot to reply. :P

[quote name='alvaro' timestamp='1317821198' post='4869398']
That's a clever way of computing the bit count of every 2-bit box. It's probably not better in practice than [code]x = ((x & 0x55555555) + ((x >> 1) & 0x55555555));[/code][/quote]
Makes sense.

[quote]
If you think of your 32-bit number as a 4-digit number in base 256, you are computing
[...]
e, f and g are lost in overflow, so by shifting 24 places to the right, you recover h, and h = a + b + c + d.[/quote]
Yeah, it finally clicked for me while I was showering that night. (Oh man, realizing a solution to a computer science problem is just an incredible feeling!)

[quote]
Yes, and if you understand the 32-bit code, you should be able to write the 64-bit version yourself.
[/quote]
The main source of confusion was from the multiplication of 0x1010101, which I kept seeing as a decimal magic number. "What significance does multiplying a number by 16843009 have? It just seems so arbitrary!"

Thanks again for clearing this up. :D

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this