源碼為
public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}
該方法的作用是將i的二進制表示的數(shù)前面的0的個數(shù)返回,
由于負數(shù)第一位符號位是1,所以必然返回0
if (i >>> 16 == 0) { n += 16; i <<= 16; }
i >>> 16,這表示i向右移動16位衅谷,與i>>16不同
'>>右移時如果是正數(shù)會補0,負數(shù)會補1似将,而>>>只會補0,舉例
8>>2 = 0100 -> 0001
8>>>2 = 0100 -> 0001
-8>>2 = 1100 -> 1111 //實際上負數(shù)是以補碼形式保存,這里只是舉例
-8>>>2 = 1100 -> 0011 // 高位補0
在看源碼
i >>> 16 == 0
// 00000000 00000000 00000000 00000000
實際上表示的是前16位為0蚀苛,
i <<= 16
表示將i左移16位后再賦值給i在验,整句的意思是如果i前16位為0,則把后16位移動到前16位堵未,并給后16位補0腋舌。
通俗點講就是,先判斷前面16位是不是0渗蟹,如果是0就把前16位去掉块饺,后面的頂上赞辩。
后續(xù)的
if (i >>> 24 == 0) { n += 8; i <<= 8; }
i>>>24實際上判斷的是8位,之后再判斷前4位授艰,再判斷前2位
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
n就是統(tǒng)計0的數(shù)量辨嗽,但是我們注意到n的初始值為1,按理說不應(yīng)該是0嗎淮腾?
原因在最后一句糟需,如果i>>>31即i的末位是0的話,n應(yīng)該要再加上1谷朝,但是這里實際上是減去了末位的值0洲押,即少加了1,而如果末位的值是1本應(yīng)該跳過圆凰,但這里卻多減了1杈帐,所以n的初始值不是0而是1.
n -= i >>> 31;
也可以看做
if (i >>> 31 == 1) { n -= 1; }
至于作者為什么要這樣寫,不得而知专钉,如果你有什么看法歡迎留言討論~
如果把n的初始值設(shè)為0挑童,這個方法也可以這么寫
public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 0;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
if (i >>> 31 == 0) { n += 1;};
return n;
}
這種二分判斷法方法讓原來需要比較32次減少至比較5次,大大提高了效率
它還有一個姐妹方法驶沼,統(tǒng)計從右邊開始的0個數(shù)炮沐,類似就不再敘述了
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);
}