方法功能:获取指定整数转换成二进制后的尾随零的个数。
比如数字8的二进制是0000 0000 0000 0000 0000 0000 0000 1000,那么可以得到它的尾随0有3位,最后三位是000。
该方法的源码如下:
/**
* Returns the number of zero bits following the lowest-order ("rightmost")
* one-bit in the two's complement binary representation of the specified
* {@code int} value. Returns 32 if the specified value has no
* one-bits in its two's complement representation, in other words if it is
* equal to zero.
*
* @param i the value whose number of trailing zeros is to be computed
* @return the number of zero bits following the lowest-order ("rightmost")
* one-bit in the two's complement binary representation of the
* specified {@code int} value, or 32 if the value is equal
* to zero.
* @since 1.5
*/
public static int numberOfTrailingZeros(int i) {
// HD, Figure 5-14
int y;
if (i == 0) return 32;
int n = 31;
y = i <<16; if (y != 0) { n = n -16; i = y; }
y = i << 8; if (y != 0) { n = n - 8; i = y; }
y = i << 4; if (y != 0) { n = n - 4; i = y; }
y = i << 2; if (y != 0) { n = n - 2; i = y; }
return n - ((i << 1) >>> 31);
}
对该方法进行注释:
/**
* 即计算整数的尾随零的个数
* 返回指定int值的二进制补码二进制表示形式中最低位(“最右边”)一位之后的零位数目。 如果指定值的二进制补码表示中没有一位(即等于零),则返回32。
* 比如数字8的二进制是0000 0000 0000 0000 0000 0000 0000 1000,那么可以得到它的尾随零为3
*
* @param i 要计算其尾随零的数量的值
* @return 指定的int值的二进制补码二进制表示形式中最低位(“最右”)一位之后的零位数目;如果该值等于零,则为32。
*/
public static int numberOfTrailingZeros(int i) {
// 局部变量,临时保存将i左移n(n可能是16、8、4、2)位后的结果
int y;
// 快速处理,如果i为0,表示32位都是0,那么不进行下面的判断,直接返回32
if (i == 0) return 32;
// 局部变量,记录尾随零的个数
int n = 31;
// 用变量y保存i左移16位后的值
// 例如:数字1的二进制是 0000 0000 0000 0000 0000 0000 0000 0001
// 左移16位后的二进制是 0000 0000 0000 0001 0000 0000 0000 0000
y = i << 16;
if (y != 0) {// 判断i左移16位后的结果是否等于0,如果等于0表示倒数第一个非零值在高16位,如果不等于0表示倒数第一个非零值在低16位
// 执行到这里,表示倒数第一个非零值在低16位,所以n减去16,因为高16位全是0,需要记录
n = n - 16;
// 然后将低16位全部左移到高16位,为了下面继续判断尾随零的个数
i = y;
}
// 左移8位后的二进制是 0000 0001 0000 0000 0000 0000 0000 0000
y = i << 8;
if (y != 0) {// 判断i左移8位后的结果是否等于0,如果等于0表示倒数第一个非零值在高8位,如果不等于0表示倒数第一个非零值在低8位
// 执行到这里,表示倒数第一个非零值在低8位,所以n减去8,因为高8位全是0,需要记录
n = n - 8;
// 然后将低8位全部左移到高8位,为了下面继续判断尾随零的个数
i = y;
}
// 左移4位后的二进制是 0001 0000 0000 0000 0000 0000 0000 0000
y = i << 4;
if (y != 0) {// 判断i左移4位后的结果是否等于0,如果等于0表示倒数第一个非零值在高4位,如果不等于0表示倒数第一个非零值在低4位
// 执行到这里,表示倒数第一个非零值在低4位,所以n减去4,因为高4位全是0,需要记录
n = n - 4;
// 然后将低4位全部左移到高4位,为了下面继续判断尾随零的个数
i = y;
}
// 左移2位后的二进制是 0100 0000 0000 0000 0000 0000 0000 0000
y = i << 2;
if (y != 0) {// 判断i左移2位后的结果是否等于0,如果等于0表示倒数第一个非零值在高2位,如果不等于0表示倒数第一个非零值在低2位
// 执行到这里,表示倒数第一个非零值在低2位,所以n减去2,因为高2位全是0,需要记录
n = n - 2;
// 然后将低2位全部左移到高2位,为了下面继续判断尾随零的个数
i = y;
}
// 左移1位后的二进制是 1000 0000 0000 0000 0000 0000 0000 0000
// 再无符号右移31后的二进制是 0000 0000 0000 0000 0000 0000 0000 0001
return n - ((i << 1) >>> 31);
}
其实这个方法就是利用位运算求尾随零的个数,思路就是不断进行二分来记录统计尾随零的出现次数。
画了一个图,可能方便理解些: