Hacker's Delight

5-3. Counting Leading 0’s

There are several simple ways to count leading 0’s with a binary search technique. Below is a model that has several variations. It executes in 20 to 29 instructions on the basic RISC. The comparisons are “logical” (unsigned integers).

if (x == 0) return(32); 
n = 0; 
if (x <= 0x0000FFFF) {n = n +16; x = x <<16;} 
if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;} 
if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;} 
if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;} 
if (x <= 0x7FFFFFFF) {n = n + 1;} 
return n; 

One variation is to replace the comparisons with and’s:

if ((x & 0xFFFF0000) == 0) {n = n +16; x = x <<16;} 
if ((x & 0xFF000000) == 0) {n = n + 8; x = x << 8} 
... 

Another variation, which avoids large immediate values, is to use ...