面試題：jdk那些類的底層實現(xiàn)使用過位運算，并且給你印象最深？
來自：Java面試那些事兒
咱們先從一道簡單的面試題說起。
請?zhí)畛浯a，判斷一個數(shù)是否為奇數(shù)。
public static boolean isOdd(int i) {}
估計很多同學(xué)一看到這道題目，都會覺得太簡單了，簡直就是送分題，恰恰也是這么簡單的一道題目，卻能慢慢引導(dǎo)出來很多問題。
我相信很多同學(xué)的答案，可能是這樣的。
public static boolean isOdd(int i) {if ( i % 2 == 1) {return true;} else {return false;}}
咋一看，似乎沒有毛病，但一推敲，似乎哪里出錯？奇數(shù)是有正負(fù)之分的，那么這個寫法似乎漏掉了負(fù)奇數(shù)。
那還不簡單，直接這么寫不就可以了嗎。
public static boolean isOdd(int i) {if ( i % 2 == 1 || i % 2 == -1 ) {return true;} else {return false;}}
這種寫法，估計多半是長期寫業(yè)務(wù)代碼，形成的思維（這病得治）。如果我是面試官的話，可能會問他，if條件句里面的表達(dá)式既然已經(jīng)是boolean類型了，為什么還要多此一舉呢？一些同學(xué)可能會改成這樣。
public static boolean isOdd(int i) {return i % 2 == 1 || i % 2 == -1;}
到了這一步，我估計會問他，這個表達(dá)式還能優(yōu)化嗎？腦子靈活的同學(xué)，可能會給出這個答案。
public static boolean isOdd1(int i) {return (i % 2) != 0;}
到這里，我可能會問他，還能有其它寫法嗎？如果他一時寫不出來，我會提示他，計算機里面的所有數(shù)據(jù)都是以二進(jìn)制的形式來存儲的，那么奇數(shù)與偶數(shù)說到底也是二進(jìn)制，你要不試著用位運算來實現(xiàn)。
有的同學(xué)，會給我這個答案。
public static boolean isOdd(int i) {return i >> 1 << 1 != i;}
也有的同學(xué)，會給我這個答案。
public static boolean isOdd(int i) {return (i & 1) == 1;}
如果是你，你會更傾向于那種答案呢？
好了，既然咱們聊到了位運算，那我再拋給你一個問題。
jdk提供的常用類里，那些類的底層實現(xiàn)使用過的位運算給你印象最深？
我相信很多同學(xué)都會以HashMap來舉例說明，要問為什么，因為這個已經(jīng)被各個面試官翻來覆去的問，所以，沒有去讀過HashMap的同學(xué)應(yīng)該是少之又少。
這里以 1.7 的HashMap為例，有一個典型的例子，計算key對應(yīng)的數(shù)組下標(biāo)時，用位運算來代替求余操作。
/*** Returns index for hash code h.*/static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);}
length must be a non-zero power of 2，注意到注釋里面的英文沒有？
當(dāng)容量是2^n時，h & (length - 1) == h % length 這個表達(dá)式就成立了。
這么做有兩個效果。
位運算效率非常高。在《編程珠璣》這本書里，曾說過模運算花費的時間大概是算術(shù)運算的10倍左右。
保證了元素在哈希表中均勻地散列。
jdk1.8里HashMap的tableSizeFor也用到了位運算。
static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}
HashMap的hash計算也用到了位運算。還有集合類的擴容也經(jīng)常用到了位運算。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
同樣在并發(fā)中，也有很多地方用到了位運算，而且很巧妙，比如下面這兩個代表。
ThreadPoolExecutor中ctl變量的設(shè)計確實精美，用高3位表示線程池的運行狀態(tài)，低29位表示線程池中線程數(shù)。
private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0));private static final int COUNT_BITS = Integer.SIZE - 3;private static final int CAPACITY = (1 << COUNT_BITS) - 1;// runState is stored in the high-order bitsprivate static final int RUNNING = -1 << COUNT_BITS;private static final int SHUTDOWN = 0 << COUNT_BITS;private static final int STOP = 1 << COUNT_BITS;private static final int TIDYING = 2 << COUNT_BITS;private static final int TERMINATED = 3 << COUNT_BITS;// Packing and unpacking ctlprivate static int runStateOf(int c) { return c & ~CAPACITY; }private static int workerCountOf(int c) { return c & CAPACITY; }private static int ctlOf(int rs, int wc) { return rs | wc; }
同樣的設(shè)計，還有讀寫鎖ReentrantReadWriteLock內(nèi)部的同步容器框架Sync中的讀寫狀態(tài)state，分成高16位與低16位，其中高16位表示讀鎖個數(shù)，低16位表示寫鎖個數(shù)。
static final int SHARED_SHIFT = 16;static final int SHARED_UNIT = (1 << SHARED_SHIFT);static final int MAX_COUNT = (1 << SHARED_SHIFT) - 1;static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;/** Returns the number of shared holds represented in count */static int sharedCount(int c) { return c >>> SHARED_SHIFT; }/** Returns the number of exclusive holds represented in count */static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
除此之外，還有我們常用的包裝類Integer 、Long等，里面就有很多位操作。比如這些方法highestOneBit、lowestOneBit、numberOfLeadingZeros、bitCount、reverse等。依次類推還有很多跟數(shù)學(xué)相關(guān)的類都用到了。
最后，還得要提一個類BitSet，里面有很多位運算的操作，在一些海量數(shù)據(jù)處理的時候，可能用得著。
你深入去分析，就會發(fā)現(xiàn)，哇，這么多地方都用到了啊。
現(xiàn)在，有沒有覺得jdk源碼原來如此有趣！
特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
