Another of my favorite tricks - reducing the number of bits in a number by 1

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Anon, et cetera — Thu, 13 Oct 2005 23:44:24 GMT

How useful do you feel interview questions like the one mentioned above are? Why?

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Nicholas Allen — Thu, 13 Oct 2005 23:44:26 GMT

Interesting observation. So I decided to think about why x & (x - 1) has one fewer bit set if x != 0. Here's why:

x != 0 so x has at least one bit set.

From right-to-left, x has some number of 0 bits at the end (0-31), a 1 bit, and the rest of the bits. Call the rest of the bits a.

So, x looks like a10...0.

x - 1 is going to flip all the 0 bits on the right until it can borrow the rightmost 1 bit.

So, x - 1 looks like a01...1.

a10...0 & a01...1 = a00...0, which is the same as x except we killed the rightmost 1 bit. Thus, x & (x - 1) has one fewer set bit than x.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Aaron — Fri, 14 Oct 2005 00:05:15 GMT

Bitwise operations are fun.

What you're doing, (x & (x - 1)), removes the lowest bit.

My favorite one is (x & -x) which isolates the bottom bit.

My most useful operation with this? ((x & -x) == x)... returns true if x is a power of 2 (or equal to 0) -- very useful for quick assertions that the world is sane.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

LarryOsterman — Fri, 14 Oct 2005 00:29:28 GMT

Anon, I used to use this one exclusively for several years.

The reason I like it is because it's a remarkably open-ended question - usually the interviewee starts with an interative loop that counts the bits taking 32 iterations. Then you ask them to make it faster, which usually adds an early out.

Then you ask them to make it still faster. Now things get interesting. A good candidate will pull into their bag of tricks and come up with a lookup table. You then ask them how big the lookup table, and hopefully they'll realize that they're looking at a 4G lookup table and they can then figure out how to reduce the size of the table.

Nicholas, thanks!

re: Another of my favorite tricks - reducing the number of bits in a number by 1

tzagotta — Fri, 14 Oct 2005 00:50:32 GMT

Interesting post. Thanks Larry.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

nar — Fri, 14 Oct 2005 01:19:11 GMT

A better interview question would be: Why does x = x & (x - 1) reduce the number of bits by one? Test it on yourself. :)

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Norman Diamond — Fri, 14 Oct 2005 05:32:44 GMT

Regarding the first trick:

> It's a silly trick, but clever.

Yes and yes. But if the numeric values are distributed uniformly, then each bit will be as likely to be a 1 as a 0, so that loop will still iterate 16 times on average. Of course there are reasons why the numeric values usually aren't distributed uniformly and usually less than half the bits are 1s, but your loop might still iterate more times than you were thinking. A lookup table on bytes will still beat it.

I wouldn't have thought of the trick that your colleagues came up with though. Its cleverness outranks its silliness and that looks like amazing code.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

vcv — Fri, 14 Oct 2005 06:16:59 GMT

Wouldn't this also work?

{
bitcount = 0;
while (value != 0)
{
value >>= 1;
bitcount++;
}
return bitcount;
}

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Dominic Cronin — Fri, 14 Oct 2005 08:54:04 GMT

OK - I'll be the dummy :-)

Why on earth would you want to count the number of bits in a number? Is this something you would do in a real situation, or just in Microsoft interviews?

re: Another of my favorite tricks - reducing the number of bits in a number by 1

denis — Fri, 14 Oct 2005 15:13:09 GMT

vcv: that gets the highest bit set.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Carlos — Fri, 14 Oct 2005 15:55:09 GMT

vcv wrote "Wouldn't this also work?"

No. It returns the position of the most significant 1 bit.

The best solution to Larry's question "How quickly can you count the bits in a 16 (or 32) bit integer?" is:

int CountBits(int value)
{
return sizeof(value) * 8;
}

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Jonas Grumby — Fri, 14 Oct 2005 18:16:53 GMT

Does the "fastest known version", beat all lookup-based solutions? 4GB might be excessive overhead just for bit counting, but byte-based tables/switches could be reasonable, and presumably faster (or am I wrong about that?).

re: Another of my favorite tricks - reducing the number of bits in a number by 1

BlackTigerX — Fri, 14 Oct 2005 18:31:08 GMT

>>Wouldn't this also work?

wouldn't that return always the same value?

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Anonymous — Fri, 14 Oct 2005 18:38:55 GMT

To the original question, I think a sharp interview candidate could have quickly answered immediately 16 (or 32). Because you didn't ask him how to count how many bits *are set* in the integer. Simply count the bits. (grin).

"How quickly can you count the bits in a 16 (or 32) bit integer?"

re: Another of my favorite tricks - reducing the number of bits in a number by 1

LarryOsterman — Fri, 14 Oct 2005 19:35:21 GMT

Jonas, on most machines, I'm pretty sure that the bit twiddling version will be faster (but I've not tested it). This is because the bit twidling version does its work entirely in registers, while a lookup table has to hit memory (to look values up in the table). In general, going to memory is going to be slower than accessing data in registers.

It takes about 15 instructions to do the shift and adds (even for a 32bit number), even if you unroll the loop and look up in an 8bit table, you're going to have 4 memory accesses to a 256 byte large table (which means you're likely to blow the L1 cache hitting the table).

How's this?

Maurits — Fri, 14 Oct 2005 19:37:49 GMT

Rough draft
Assumes Win32 (32-bit ints), fails on 64-bit machines

I use leading underscores to preserve indenting (sorry, but this blog software eats leading spaces)

// bits.h
int bitsinchar(unsigned char);
int bitsinint(unsigned int);

// bits.c
int bitsinint(unsigned int i)
{
__// count char-by-char... assumes four-byte int
__// if this is a 64-bit int then extend the pattern accordingly
__return
____bitsinchar((char)(i & 0xff)) +
____bitsinchar((char)(i >> 8 & 0xff)) +
____bitsinchar((char)(i >> 16 & 0xff)) +
____bitsinchar((char)(i >> 24 & 0xff))
__;
}

// c must be an eight-bit char... no wchar's here
int bitsinchar(unsigned char c)
{
__// 256-entry lookup table
__select (c)
__{
____// eight bits
____case 0xff:
______return 8;

____// seven bits
____case 0xfe:
____case 0xfd:
____// ... eight cases...
____case 0x7f:
______return 7;

____// six bits... (eight-choose-two-cases)

____// five bits... (eight-choose-three-cases)

____// four bits... (eight-choose-four-cases)

____// three bits... (eight-choose-three-cases)

____// two bits... (eight-choose-two-cases)

____// one bit...
____case 0x80:
____case 0x40:
____// more cases...
____case 0x02:
____case 0x01:
______return 1;

____// zero bits
____case 0: return 0;

__}

}

OK, you answered my question... :)

Maurits — Fri, 14 Oct 2005 19:55:52 GMT

You answered my question while I was typing it out: :)
> even if you unroll the loop and look up in an 8bit table, you're going to have 4 memory accesses to a 256 byte large table (which means you're likely to blow the L1 cache hitting the table)

How about an 8-entry lookup table?

Maurits — Fri, 14 Oct 2005 20:03:10 GMT

typedef char nybble;

int bitsinnybble(nybble n)
{
// 8-entry lookup table
__select (n)
__{
____// four bits
____case 0xf:
______return 4;

____// three bits
____case 0xe:
____case 0xd:
____case 0xb:
____case 0x7:
______return 3;

____// two bits
____case 0xc:
____case 0xa:
____case 0x9:
____case 0x6:
____case 0x5:
____case 0x3:
______return 3;

____// one bit
____case 0x8:
____case 0x4:
____case 0x2:
____case 0x1:
______return 1;

____// zero bits
____case 0:
______return 0;
}

int bitsinchar(unsigned char c)
{
__return
____bitsinnybble((nybble)(c & 0xf)) +
____bitsinnybble((nybble)(c >> 4 & 0xf))
__;
}

stupid bug fix

Maurits — Fri, 14 Oct 2005 20:36:40 GMT

Er, I mean, a 16-entry lookup table (not 8-entry)
Also, the two-bit cases should return 2, not 3

re: Another of my favorite tricks - reducing the number of bits in a number by 1

SomeBody — Fri, 14 Oct 2005 20:53:36 GMT

If you're going to count the bits in numerous bytes at a time, the lookup table will get cached and thus be extremely fast (assuming a small lookup table, not the 4GB one).

Even with counting a single byte, the lookup table version could be faster than the loop version depending on the characteristics of the data. There are multiple instructions in the loop and the loop will get executed as many times as there are bits. For larger numbers of bits, the loop version will have to execute more instructions than the memory access penalty of the lookup table -- memory access isn't *that* slow.

I've heard this same discussion in the past and at one time benchmarked the loop version, the parallel version, and the lookup table version over a large set of integers (Pentium 4, VC7). The lookup table version blew the others away.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Mark Wan — Fri, 14 Oct 2005 23:19:37 GMT

I am interested to know the intent of asking questions like this in an interview situation. If the intent is to make the candidate sweat and see how she reacts that is probably fine. If the intent is to see how well they problem solve it might not work. Prior knowledge of similar problems or problem patterns might affect the performance of a candidate. I try to stay away from specific questions as a gauge for talent when I conduct interviews.

Also fastest solution does not always mean fewest lines of code. Sometimes fastest solution means tweaking the implementation to a point that it could not be well understood. Well, as an application developer I do not encourage such practices until there is a critical need for such implementation. To me maintainability and code readability are more important than raw performance numbers.

Mark.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Roozbeh Ghaffari — Sat, 15 Oct 2005 02:20:43 GMT

Didn't get a chance to test, but this should do the trick:

input/output: eax

mov ebx,55555555h
mov edx,eax
and edx,ebx
shr eax,1
and eax,ebx
add eax,edx

mov ebx,33333333h
mov edx,eax
and edx,ebx
shr eax,2
and eax,ebx
add eax,edx

mov ebx,0f0f0f0fh
mov edx,eax
and edx,ebx
shr eax,4
and eax,ebx
add eax,edx

mov ebx,00ff00ffh
mov edx,eax
and edx,ebx
shr eax,8
and eax,ebx
add eax,edx

mov ebx,0000ffffh
mov edx,eax
and edx,ebx
shr eax,16
and eax,ebx
add eax,edx

anyone got a faster implementation?

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Roozbeh Ghaffari — Sat, 15 Oct 2005 03:26:06 GMT

Woohoo! Check this out:

in/out: eax

mov edx,eax
shr edx,1
and edx,55555555h
sub eax,edx

mov ebx,33333333h
mov edx,eax
shr edx,2
and edx,ebx
and eax,ebx
add eax,edx

mov edx,eax
shr edx,4
add eax,edx
and eax,0f0f0f0fh

mov ebx,01010101h
mul ebx
shr eax,24

re: Another of my favorite tricks - reducing the number of bits in a number by 1

LarryOsterman — Sat, 15 Oct 2005 05:33:55 GMT

Somebody, Roozbeh put a version of the parallel algorithm in the comments. It's possible that a lookup algorithm would be faster, but...

When we did the numbers (about 10 years ago, on 386 hardware), the parallel algorithm blew the lookup algorithm away completely.

With more modern processors, your results might be different.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

jeuge — Sat, 15 Oct 2005 07:01:55 GMT

Check the MIT HAKMEM count http://blogs.msdn.com/jeuge/archive/2005/06/08/HAKMEM_Bit_Count.aspx

re: Another of my favorite tricks - reducing the number of bits in a number by 1

LarryOsterman — Sat, 15 Oct 2005 17:44:27 GMT

Jeu, my eyes are bleeding, and I'm just now picking my jaw off the floor.

That was amazingly brilliant. I defy ANYONE to write a table lookup version that's shorter than that.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Ken Hirsch — Sun, 16 Oct 2005 16:49:09 GMT

There's a book, <a href="http://www.amazon.com/gp/product/0201914654/">Hacker's Delight by Henry Warren</a>, that has tons of these tricks.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Norman Diamond — Mon, 17 Oct 2005 06:50:08 GMT

Saturday, October 15, 2005 10:44 AM by LarryOsterman

> Jeu, my eyes are bleeding, and I'm just now
> picking my jaw off the floor.

You're going to drop your jaw again. Look at the algorithm of your colleagues that you described (though didn't count) in your initial posting here. 4 of the operators are shifts. Shifts can be slow, but how slow? Let's compare.

Look at the MIT HAKMEM translation into C as posted by Jeu George. 1 of the operators is an % operator, taking a remainder. A remainder as in the result of a DIVIDE. With a divider that is not a power of 2. Divides are slow. Slower than 4 shifts? I think yes, usually.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

michael — Mon, 17 Oct 2005 17:54:35 GMT

I generally prefer interview questions that prove some basic understanding of math as well as sound programming skills.

My favorite today is the not so complex ...
"Write a function for calculating the prime factors of any given integer."

Not too complex, but it shows how the person thinks and approaches code very easily.

- Michael

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Roozbeh Ghaffari — Mon, 17 Oct 2005 21:57:46 GMT

That was amazing Jeu! In assembly it's even shorter than the one that uses multiplication. I'm not sure about today's machines, but in the old days I remember DIV being much slower than MUL. That might compensate for the few extra instructions, but who cares! ;)

256-entry lookup table is the fastest

Maurits — Tue, 18 Oct 2005 03:28:03 GMT

According to this 2002 comparison of several bitcounting algorithms...
http://www-db.stanford.edu/~manku/bitcount/bitcount.html

A 256-entry lookup table is the fastest.

Oops, I misread...

Maurits — Tue, 18 Oct 2005 03:30:24 GMT

Actually the results of the comparison are that a 65Kb lookup table is the fastest.

I presume that the initialization of the lookup table is outweighed by the number of bits counted, though.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

Wally Bass — Fri, 28 Oct 2005 19:10:14 GMT

Counting "1" bits is probably not all that common, but checking whether a number is a power of 2 does occur with some frequency (in verifying a valid "sectors per cluster" value for example). Checking whether a number is a power of 2 is the same as checking whether it has exactly 1 "1" bit.

Is there a better way to check that a number has exactly 1 "1" bit than using an approach
derived from your algorithm?

re: Another of my favorite tricks - reducing the number of bits in a number by 1

David Walker — Sat, 17 Dec 2005 02:53:06 GMT

When you say "I'm not sure exactly why it works, and it only works for 2s complement numbers, but it DOES work."

Umm, you mean it only works when negative numbers are stored as the twos complement of the same positive number? It sounds like you're talkking about a set of "2s complement numbers" that maybe not all numbers fall into.

Also, somewhere in a related note, someone said that a lookup table would work, except if you're adding the bits that are "on" in a 32-bit fullword, you'd need a huge lookup table. I would simply think of the 32-bit word as eight 4-bit chunks, and use a 16-entry lookup table for each of the 4-bit chunks. Eight lookups and eight additions, plus some looping overhead.

In fact, I solved the same problem that way in production IBM mainframe code many years ago. (This was for something that was infrequently used... In fact, it was used once per customer to count something, and then a flag was set to never call the routine again.)

David W.

re: Another of my favorite tricks - reducing the number of bits in a number by 1

David Walker — Sat, 17 Dec 2005 02:59:31 GMT

Edit -- it wasn't someone somewhere, it was you, Larry, in a comment in this blog. Duh. I thought that's where I read it, then I missed it when I looked, oh well.

Spending scads of time optimizing a function like this might not be a good use of time -- depending on the use of course. We decided that our 4-bit-at-a-time lookup function was the perfect balance between being simple to write and (importantly) to understand, and being plenty fast.

Larry Osterman s WebLog Another of my favorite tricks reducing the | Patio Chairs

Wed, 03 Jun 2009 05:26:32 GMT

PingBack from http://patiochairsite.info/story.php?id=29037

Larry Osterman s WebLog Another of my favorite tricks reducing the | patio set

Larry Osterman s WebLog Another of my favorite tricks reducing the | patio set — Thu, 18 Jun 2009 05:16:48 GMT

PingBack from http://patiosetsite.info/story.php?id=160

Larry Osterman s WebLog Another of my favorite tricks reducing the | patio umbrella

Thu, 18 Jun 2009 07:06:23 GMT

PingBack from http://patioumbrellasource.info/story.php?id=1777

Larry Osterman s WebLog Another of my favorite tricks reducing the | debt solutions

Fri, 19 Jun 2009 20:53:29 GMT

PingBack from http://debtsolutionsnow.info/story.php?id=1308