count leading zeros (clz) or number of leading zeros (nlz) in Java

Question

I need int 32 in binary as 00100000 or int 127 in binary 0111 1111. The variant Integer.toBinaryString returns results only from 1. If I build the for loop this way:

for (int i= 32; i <= 127; i + +) {
System.out.println (i); 
System.out.println (Integer.toBinaryString (i));
}

And from binary numbers I need the number of leading zeros (count leading zeros (clz) or number of leading zeros (nlz)) I really meant the exact number of 0, such ex: at 00100000 -> 2 and at 0111 1111 - > 1

Consider _formatting_ the output so as to put leading zeros. — devnull, Jan 25 '14 at 12:59

score 11 · Answer 1 · answered Jan 25 '14 at 13:33

11

How about

int lz = Integer.numberOfLeadingZeros(i & 0xFF) - 24;
int tz = Integer.numberOfLeadingZeros(i | 0x100); // max is 8.

answered Jan 25 '14 at 13:33

Peter Lawrey

525,659
79
751
1,130

Martijn Courteaux · Accepted Answer · 2015-10-29T09:42:22.977

1

Count the number of leading zeros as follows:

int lz = 8;
while (i)
{
    lz--;
    i >>>= 1;
}

Of course, this supposes the number doesn't exceed 255, otherwise, you would get negative results.

edited Oct 29 '15 at 09:42

answered Jan 25 '14 at 13:02

Martijn Courteaux

67,591
47
198
287

This approach is very slow as it creates a temporary String object. Using Integer methods is the recommended approach. – antiguru Mar 09 '15 at 09:49
1

@antiguru: After seeing this almost two year later, I decided that I must change it. This was too horrible. – Martijn Courteaux Oct 29 '15 at 09:43

Sravan U · Answer 3 · 2014-01-26T13:11:08.510

1

Efficient solution is int ans = 8-(log₂(x)+1)

you can calculate log₂(x)= log_y (x) / log_y (2)

edited Jan 26 '14 at 13:11

answered Jan 26 '14 at 06:50

Sravan U

67
1
7

This solution is almost equal to the solution given by @Martijn Courteaux, log₂(x) gives you the length of the binaryString(x) without leading zeros. so 8 - lengthOfString_WithoutLeadingZeroes gives your answer – Sravan U Jan 26 '14 at 11:19
What do you mean, the correct solution for 32 is 3, its working right! – Sravan U Jan 26 '14 at 12:02
Okay, I didn't notice that binary counting starts with pow(2,0) , so subtract one from the answer, and the answer should be strictly integer and do not round it off. – Sravan U Jan 26 '14 at 12:11
1

What an excellent answer! I would upvote multiple times if I could. Thank you! – ayanami Apr 30 '18 at 19:28

ceph3us · Answer 4 · 2016-06-27T14:05:17.487

public class UtilsInt {

    int leadingZerosInt(int i) {
        return leadingZeros(i,Integer.SIZE);
    }

    /**
     * use recursion to find occurence of first set bit
     * rotate right by one bit & adjust complement
     * check if rotate value is not zero if so stop counting/recursion
     * @param i - integer to check 
     * @param maxBitsCount - size of type (in this case int)
     *                       if we want to check only for:
     *                         positive values we can set this to Integer.SIZE / 2   
     *                         (as int is signed  in java - positive values are in L16 bits)
     */
     private synchronized int leadingZeros(int i, int maxBitsCount) {
         try {
            logger.debug("checking if bit: "+ maxBitsCount 
                                + " is set | " + UtilsInt.intToString(i,8));
            return (i >>>= 1) != 0 ? leadingZeros(i, --maxBitsCount) : maxBitsCount;
         } finally {
             if(i==0) logger.debug("bits in this integer from: " + --maxBitsCount 
                               + " up to last are not set (i'm counting from msb->lsb)");
         }
    }
}

test statement:

int leadingZeros = new UtilsInt.leadingZerosInt(255); // 8

test output:

checking if bit: 32 is set |00000000 00000000 00000000 11111111
checking if bit: 31 is set |00000000 00000000 00000000 01111111
checking if bit: 30 is set |00000000 00000000 00000000 00111111
checking if bit: 29 is set |00000000 00000000 00000000 00011111
checking if bit: 28 is set |00000000 00000000 00000000 00001111
checking if bit: 27 is set |00000000 00000000 00000000 00000111
checking if bit: 26 is set |00000000 00000000 00000000 00000011
checking if bit: 25 is set |00000000 00000000 00000000 00000001
bits in this integer from: 24 up to last are not set (i'm counting from msb->lsb)

count leading zeros (clz) or number of leading zeros (nlz) in Java

4 Answers4

Linked