Bitwise problem - Help!

[while1]

A friend gave me this problem to work on and it's kind of pissing me off.  I've spent a few hours working on it but to no avail.

Basically you have to in a maximum of 40 operations (legal operations: ! ~ & ^ | + << >>) count the number of 1 bits of a word.

[iago]

How long is the word? I'm assuming 16, 32, or 64 bits?

[Camel]

I do believe theres an x86 instruction that does just that

A simple approach would be:
WORD theNumber = ?;
int bitCount = 0;

bitCount += ((theNumber) & 1);
bitCount += ((theNumber >> 1) & 1);
bitCount += ((theNumber >> 2) & 1);
bitCount += ((theNumber >> 3) & 1);
bitCount += ((theNumber >> 4) & 1);
bitCount += ((theNumber >> 5) & 1);
bitCount += ((theNumber >> 6) & 1);
bitCount += ((theNumber >> 7) & 1);
...


Although that will quickly use up your instructions.

[Camel]

num - (num >> 1) - (num >> 2) ... (num >> sizeof(num)-1)

[while1]

How long is the word? I'm assuming 16, 32, or 64 bits?

32

I do believe theres an x86 instruction that does just that

A simple approach would be:
WORD theNumber = ?;
int bitCount = 0;

bitCount += ((theNumber) & 1);
bitCount += ((theNumber >> 1) & 1);
bitCount += ((theNumber >> 2) & 1);
bitCount += ((theNumber >> 3) & 1);
bitCount += ((theNumber >> 4) & 1);
bitCount += ((theNumber >> 5) & 1);
bitCount += ((theNumber >> 6) & 1);
bitCount += ((theNumber >> 7) & 1);
...


Although that will quickly use up your instructions.

Tried that, and since word size is 32-bits and each of those statements use 3 operations each (except the first one which uses 2), that goes way over the 40 operation limit. 

[Camel]

Is this supposed to be an algorithm or a single equation?

[while1]

Is this supposed to be an algorithm or a single equation?

as long as your algorithm doesn't consist of any control structures (i.e. no if, for, etc.) and only the operations listed.

[Camel]

I think I just proved it's impossible. I'm going to stare at this a little bit longer to make sure I'm not wrong before I post it.

[edit] I'm assuming recursion isn't allowed?

[while1]

I think I just proved it's impossible. I'm going to stare at this a little bit longer to make sure I'm not wrong before I post it.

[edit] I'm assuming recursion isn't allowed?

right, it's not allowed.

[while1]

An example in terms of C/C++

Code: [Select]

int bitCount(int x) {
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
}

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
   
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Call any functions.
  4. Use any other operations, such as &&, ||, -, or ?:
  5. Use any form of casting.
 
  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.