面试题：jdk那些类的底层实现使用过位运算，并且给你印象最深？
扫描二维码
随时随地手机看文章
来自：Java面试那些事儿
咱们先从一道简单的面试题说起。
请填充代码，判断一个数是否为奇数。
public static boolean isOdd(int i) {}
估计很多同学一看到这道题目，都会觉得太简单了，简直就是送分题，恰恰也是这么简单的一道题目，却能慢慢引导出来很多问题。
我相信很多同学的答案，可能是这样的。
public static boolean isOdd(int i) {if ( i % 2 == 1) {return true;} else {return false;}}
咋一看，似乎没有毛病，但一推敲，似乎哪里出错？奇数是有正负之分的，那么这个写法似乎漏掉了负奇数。
那还不简单，直接这么写不就可以了吗。
public static boolean isOdd(int i) {if ( i % 2 == 1 || i % 2 == -1 ) {return true;} else {return false;}}
这种写法，估计多半是长期写业务代码，形成的思维（这病得治）。如果我是面试官的话，可能会问他，if条件句里面的表达式既然已经是boolean类型了，为什么还要多此一举呢？一些同学可能会改成这样。
public static boolean isOdd(int i) {return i % 2 == 1 || i % 2 == -1;}
到了这一步，我估计会问他，这个表达式还能优化吗？脑子灵活的同学，可能会给出这个答案。
public static boolean isOdd1(int i) {return (i % 2) != 0;}
到这里，我可能会问他，还能有其它写法吗？如果他一时写不出来，我会提示他，计算机里面的所有数据都是以二进制的形式来存储的，那么奇数与偶数说到底也是二进制，你要不试着用位运算来实现。
有的同学，会给我这个答案。
public static boolean isOdd(int i) {return i >> 1 << 1 != i;}
也有的同学，会给我这个答案。
public static boolean isOdd(int i) {return (i & 1) == 1;}
如果是你，你会更倾向于那种答案呢？
好了，既然咱们聊到了位运算，那我再抛给你一个问题。
jdk提供的常用类里，那些类的底层实现使用过的位运算给你印象最深？
我相信很多同学都会以HashMap来举例说明，要问为什么，因为这个已经被各个面试官翻来覆去的问，所以，没有去读过HashMap的同学应该是少之又少。
这里以 1.7 的HashMap为例，有一个典型的例子，计算key对应的数组下标时，用位运算来代替求余操作。
/*** 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);}
同样在并发中，也有很多地方用到了位运算，而且很巧妙，比如下面这两个代表。
ThreadPoolExecutor中ctl变量的设计确实精美，用高3位表示线程池的运行状态，低29位表示线程池中线程数。
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中的读写状态state，分成高16位与低16位，其中高16位表示读锁个数，低16位表示写锁个数。
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等。依次类推还有很多跟数学相关的类都用到了。
最后，还得要提一个类BitSet，里面有很多位运算的操作，在一些海量数据处理的时候，可能用得着。
你深入去分析，就会发现，哇，这么多地方都用到了啊。
现在，有没有觉得jdk源码原来如此有趣！
特别推荐一个分享架构+算法的优质内容，还没关注的小伙伴，可以长按关注一下：
长按订阅更多精彩▼
如有收获，点个在看，诚挚感谢
免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！
下载文档
