Converting function to bitwise only?

I have a function to count upper bits of a 32 bit value. So if a number is 11100011111..., the result is 3 as there are 3 ones in the most significant place before a 0 is hit.

I need to convert the function to use only bitwise operations (no if statements or while loops) and the total number of operations should be lesser than 50.

Question: How can this be converted to bitwise operations only while keeping less than 50 ops?

Here is the Code:

int count = 0;
  int i = 28;

  while(i >= 0) {
    int temp = (x>>i) & 0xF;
    i-=4;
    if(temp == 0xF) count+=4;
    else {
      int mask = 0x1;
      int a = (temp>>3) & mask;
      int b = (temp>>2) & mask;
      int c = (temp>>1) & mask;
      int d = temp & mask;

      if (a != 1) break;
        count+=1;
      if (b != 1) break;
        count+=1;
      if (c != 1) break;
        count+=1;
      if (d != 1) break;
        count+=1;
    }

Notations: I'll use the C notations for bitwise operations: $a \mathbin\& b$ (bitwise and), $a \mathbin| b$ (bitwise or), $a \mathbin\ll b$ (shift left), $a \mathbin\gg b$ (shift right). The shift operators are left-associative (e.g. $x \mathbin\gg m \mathbin\gg n = (x \mathbin\gg m) \mathbin\gg n$). The shift operations put zeroes in newly created bit positions: $a \mathbin\ll b = a \times 2^b$ and $a \mathbin\gg b = \lfloor a \times 2^{-b} \rfloor$. Sequences of digits with a line above (e.g. $\overline{11101000}$, $\overline{z^4z^3z^2z^1z^0}$) represent a number written in base 2 (binary).

If $x$ is an integer between $0$ and $2^N-1$, we say that $x$ is an $N$-bit number, and write $x = \overline{x^{N-1}x^{N-2}\ldots x^1x^0}$, i.e. $x^k$ is bit $k$ of $x$. Bits $k-1$ through $0$ constitute the $k$ least significant bits of $x$, and bits $N-1$ through $N-k$ constitute the $k$ most significant bits of $x$ (where $x$ is considered as an $N$-bit number).

Intuition

With 32 bits and 50 operations, an approach that looks at one bit of the input at a time isn't going to work. The next obvious thing to try is a recursive (dive-and-conquer approach) where you work on half the bits at a time. There are two simple ways to divide an $N$-bit number: into the $N/2$ most significant bits and the $N/2$ least significant bits, or into odd and even positions. Most/least significant looks promising, because the result counts how many most significant bits are 1.

Or we could approach the problem the other way: the result is a number between 0 and 32, a 6-bit number (for all but one input values, it's a 5-bit number). Can we find the bits of the result, one at a time?

Let $a$ be the input (a 32-bit number) and $z$ the output. Bit $5$ of $z$ is 1 iff $a$ is all-bits-1. Bit $4$ of $z$ is 1 iff the 16 most significant bits of $a$ are all 1 and $a$ is not all-bits-1. What about bit $3$? We have to discriminate on bit $4$: if it's 0, we look at the $8$ most significant bits of $a$ (with an exception when $a$ is all-bits-1); if it's 1, we look at bits $8$ through $15$ instead.

Expression in terms of bitwise operations

Let's express this in terms of bitwise operations. For the time being, assume we have a primitive operation $A_N$ on $N$-bit numbers such that $A_N(x) = 1$ if $x = 2^N-1$ (i.e. $x$ is all-bits-1) and $A_N(x) = 0$ otherwise.

• $z^5 = A_{32}(a)$

• if $z^5 = 0$ then $z^4 = 0$, else

$z^4 = A_{16}(a \mathbin\gg 16)$

• if $z^5 = 0$ then $z^4 = 0$, else

if $z^4 = 0$ then $z^3 = A_8(a \mathbin\gg (16+8))$, else

$z^3 = A_8((a \mathbin\& \overline{1111111100000000}) \mathbin\gg 8)$

That's not very orderly: at this point we're looking to express $z^4$ and $z^3$ in similar way so that a recursion pattern can emerge. Furthermore we've used conditional statements which we're going to have to eliminate somehow. What seems constant is that $z^k$ is $A_{2^k}$ of some number. So what number? At each stage, we cut some number which is a slice of $a$ in half. To compute the next bit of the result we're looking at the most significant half of one of the halves from the previous step. Let's write $a_{k+1}$ for the input to the step that computes $z^k$ (so that we start with $a_6 = a$ to compute $z_5$). Then, leaving aside for a moment the case when $a = 2^{32}-1$ (in other words, we leave aside the case when $z^5=1$):

• $a_5 = a_6$

• $z^4 = A_{16}(a_5 \mathbin\gg 16)$

• If $z^4 = 1$ then $a_4 = a_5 \mathbin\& (2^{16}-1)$, else $a_4 = a_5 \mathbin\gg 16$. It's awfully tempting to turn that 16 into $z^4 \mathbin\ll 4$, but it's on the wrong side. We could flip a bit (using xor), but this complicates the expression; instead, let's shift the other way: $a_4 = (a_5 \mathbin\& (2^{16}-1)) \mathbin\ll (z^4 \mathbin\ll 4) \mathbin\gg 4$.

And thus a pattern emerges:
$$\begin{align*}
z^k &= A_{2^k}(a_{k+1} \mathbin\gg 2^k) \\
a_k &= (a_{k+1} \mathbin\& (2^{2^k}-1)) \mathbin\ll (z^k \mathbin\ll k) \mathbin\gg k \\
\end{align*}$$

A simpler recursion

The initial case $z^5$ isn't right. It would be a simple matter to adjust the recursion pattern to accommodate it, but before doing that, I prefer to tweak the notation to reduce the number of shifts. When we compute $a_k$, we're aligning the extracted number to the right. Let's instead align to the left. Furthermore, let's drop the masking: we'll use a new predicate $B_m$ instead of $A_m$ which looks only at the appropriate bits. Define
$$ b_{k-1} = b_k \mathbin\ll (z^k \mathbin\ll k) $$
Define $B^n_m(x) = 1$ if the $2^n$-bit number $x$ has its $m$ most significant bits all set, and $B^n_m(x) = 0$ otherwise.
$$ z^k = B^n_{2^k}(b_k) $$

For a 32-bit number ($n=5$), we start with $b_5 = a$ and $z^5 = B^5_{32}(b_5)$ (check all 32 bits). Next we compute $b_4 = b_5 \mathbin\ll (z^5 \mathbin\ll 5)$; when $z^5=1$ (i.e. $a=2^n-1$) that sets $b_4 = 0$. We can then compute $z^4 = B^5_{16}(b_4)$ (look at the most significant 16 bits), then either $b_3 = b_4$ or $b_3 = b_4 \mathbin\ll 16$ depe

StackExchange Computer Science Q#3484, answer score: 7