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 ...

Get Hacker's Delight now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.