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

時間：2020-05-06 11:39:07

關鍵字：位運算 BSP STATIC RETURN

手機看文章

掃描二維碼
隨時隨地手機看文章

[導讀]來自：Java面試那些事兒咱們先從一道簡單的面試題說起。請?zhí)畛浯a，判斷一個數(shù)是否為奇數(shù)。 public?static?boolean?isOdd(int?i)?{ } 估計很多同學一看到這道題目，都會覺得太簡單了，簡直就是送分題，恰恰也是這么簡單的一道題目，卻能慢慢引導出來很多問

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

來自：Java面試那些事兒

咱們先從一道簡單的面試題說起。

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

public static boolean isOdd(int i) {
}

估計很多同學一看到這道題目，都會覺得太簡單了，簡直就是送分題，恰恰也是這么簡單的一道題目，卻能慢慢引導出來很多問題。

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

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

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

那還不簡單，直接這么寫不就可以了嗎。

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

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

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

到了這一步，我估計會問他，這個表達式還能優(yōu)化嗎？腦子靈活的同學，可能會給出這個答案。

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

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

有的同學，會給我這個答案。

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

也有的同學，會給我這個答案。

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

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

好了，既然咱們聊到了位運算，那我再拋給你一個問題。

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

我相信很多同學都會以HashMap來舉例說明，要問為什么，因為這個已經被各個面試官翻來覆去的問，所以，沒有去讀過HashMap的同學應該是少之又少。

這里以 1.7 的HashMap為例，有一個典型的例子，計算key對應的數(shù)組下標時，用位運算來代替求余操作。

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

當容量是2^n時，h & (length - 1) == h % length 這個表達式就成立了。

這么做有兩個效果。

位運算效率非常高。在《編程珠璣》這本書里，曾說過模運算花費的時間大概是算術運算的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計算也用到了位運算。還有集合類的擴容也經常用到了位運算。

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

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

ThreadPoolExecutor中ctl變量的設計確實精美，用高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; }

同樣的設計，還有讀寫鎖ReentrantReadWriteLock內部的同步容器框架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; }