Does Unsigned interger is playing a crucial role here in this code?


I am trying to find number of trailing zero's in a number in java. I got this code from hacker's delight. But can't understand it. As per hackers delight(Section 5-4) this should give the number of Trailing zeros.

int numOfTrailingZeros=32-numOfLeadingZeros(~(n&(n-1)))

I tried for 56 its giving me 32. Here is my numOfLeading 0 implementation in hacker's delight the parameter to method numOfLeadingZeros was unsigned integer. is it playing a big role in the method and can anyone explain me how is it working?

public static int numOfLeadingZeros(int x){
                    int n;
                    if(x==0) return (32);
                    if((x & 0x0000FFFF) == 0) { n=n+16; x=x>>16;}
                    if((x & 0x000000FF) == 0) { n=n+8; x=x>>8;}
                    if((x & 0x0000000F) == 0) { n=n+4; x=x>>4;}
                    if((x & 0x00000003) == 0) { n=n+2; x=x>>2;}
                    return n - (x & 1);

1 Answer


I'm not sure why you can assume that 32 (word size) - Trailing 0's is equal to Leading 0s?

Signed Integers have a sign bit, effectively. They use a binary encoding structure called "two's complement". If you're looking for the number of leading or trailing zero's in it's binary representation, then no, the unsigned integer/signed integer doesn't matter. (edit: it's especially irrelevant if you never pass a negative number or positive number > half the 2^word_size). However, 56 is 0b00111000, which when &'ed with 0b00110111 is just 0b00110000. Negating (~) that produces mostly 0b1's except for the fifth and sixth bit, so there would be no leading zeros.)

This is because that the fundamental assembly operations for signed and unsigned math are essentially the same except for how it affects the carry bit. Therefore, when you're trying to analyze the binary structure of something, it's type becomes largely irrelevant except for its data width.

answered on Stack Overflow Oct 4, 2017 by Andrew Pikul

User contributions licensed under CC BY-SA 3.0