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 the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.