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