面試題：jdk那些類的底層實(shí)現(xiàn)使用過(guò)位運(yùn)算，并且給你印象最深？

來(lái)自：Java面試那些事兒

咱們先從一道簡(jiǎn)單的面試題說(shuō)起。

請(qǐng)?zhí)畛浯a，判斷一個(gè)數(shù)是否為奇數(shù)。

public static boolean isOdd(int i) {
}

估計(jì)很多同學(xué)一看到這道題目，都會(huì)覺(jué)得太簡(jiǎn)單了，簡(jiǎn)直就是送分題，恰恰也是這么簡(jiǎn)單的一道題目，卻能慢慢引導(dǎo)出來(lái)很多問(wèn)題。

我相信很多同學(xué)的答案，可能是這樣的。

public static boolean isOdd(int i) { if ( i % 2 == 1) { return true; } else { return false; }}

咋一看，似乎沒(méi)有毛病，但一推敲，似乎哪里出錯(cuò)？奇數(shù)是有正負(fù)之分的，那么這個(gè)寫(xiě)法似乎漏掉了負(fù)奇數(shù)。

那還不簡(jiǎn)單，直接這么寫(xiě)不就可以了嗎。

public static boolean isOdd(int i) { if ( i % 2 == 1 || i % 2 == -1 ) { return true; } else { return false; }}

這種寫(xiě)法，估計(jì)多半是長(zhǎng)期寫(xiě)業(yè)務(wù)代碼，形成的思維（這病得治）。如果我是面試官的話，可能會(huì)問(wèn)他，if條件句里面的表達(dá)式既然已經(jīng)是boolean類型了，為什么還要多此一舉呢？一些同學(xué)可能會(huì)改成這樣。

  public static boolean isOdd(int i) { return i % 2 == 1 || i % 2 == -1; }

到了這一步，我估計(jì)會(huì)問(wèn)他，這個(gè)表達(dá)式還能優(yōu)化嗎？腦子靈活的同學(xué)，可能會(huì)給出這個(gè)答案。

 public static boolean isOdd1(int i) { return (i % 2) != 0; }

到這里，我可能會(huì)問(wèn)他，還能有其它寫(xiě)法嗎？如果他一時(shí)寫(xiě)不出來(lái)，我會(huì)提示他，計(jì)算機(jī)里面的所有數(shù)據(jù)都是以二進(jìn)制的形式來(lái)存儲(chǔ)的，那么奇數(shù)與偶數(shù)說(shuō)到底也是二進(jìn)制，你要不試著用位運(yùn)算來(lái)實(shí)現(xiàn)。

有的同學(xué)，會(huì)給我這個(gè)答案。

public static boolean isOdd(int i) { return i >> 1 << 1 != i;}

也有的同學(xué)，會(huì)給我這個(gè)答案。

public static boolean isOdd(int i) { return (i & 1) == 1;}

如果是你，你會(huì)更傾向于那種答案呢？

好了，既然咱們聊到了位運(yùn)算，那我再拋給你一個(gè)問(wèn)題。

jdk提供的常用類里，那些類的底層實(shí)現(xiàn)使用過(guò)的位運(yùn)算給你印象最深？

我相信很多同學(xué)都會(huì)以HashMap來(lái)舉例說(shuō)明，要問(wèn)為什么，因?yàn)檫@個(gè)已經(jīng)被各個(gè)面試官翻來(lái)覆去的問(wèn)，所以，沒(méi)有去讀過(guò)HashMap的同學(xué)應(yīng)該是少之又少。

這里以 1.7 的HashMap為例，有一個(gè)典型的例子，計(jì)算key對(duì)應(yīng)的數(shù)組下標(biāo)時(shí)，用位運(yùn)算來(lái)代替求余操作。

/** * 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，注意到注釋里面的英文沒(méi)有？

當(dāng)容量是2^n時(shí)，h & (length - 1) == h % length 這個(gè)表達(dá)式就成立了。

這么做有兩個(gè)效果。

1. 位運(yùn)算效率非常高。在《編程珠璣》這本書(shū)里，曾說(shuō)過(guò)模運(yùn)算花費(fèi)的時(shí)間大概是算術(shù)運(yùn)算的10倍左右。

2. 保證了元素在哈希表中均勻地散列。

jdk1.8里HashMap的tableSizeFor也用到了位運(yùn)算。

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ì)算也用到了位運(yùn)算。還有集合類的擴(kuò)容也經(jīng)常用到了位運(yùn)算。

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

同樣在并發(fā)中，也有很多地方用到了位運(yùn)算，而且很巧妙，比如下面這兩個(gè)代表。

ThreadPoolExecutor中ctl變量的設(shè)計(jì)確實(shí)精美，用高3位表示線程池的運(yùn)行狀態(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è)計(jì)，還有讀寫(xiě)鎖ReentrantReadWriteLock內(nèi)部的同步容器框架Sync中的讀寫(xiě)狀態(tài)state，分成高16位與低16位，其中高16位表示讀鎖個(gè)數(shù)，低16位表示寫(xiě)鎖個(gè)數(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)的類都用到了。

最后，還得要提一個(gè)類BitSet，里面有很多位運(yùn)算的操作，在一些海量數(shù)據(jù)處理的時(shí)候，可能用得著。

你深入去分析，就會(huì)發(fā)現(xiàn)，哇，這么多地方都用到了啊。

現(xiàn)在，有沒(méi)有覺(jué)得jdk源碼原來(lái)如此有趣！

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝