移位和位运算相关算法题学习积累

最近逛博客发现几个很有意思的算法题，大都是二进制相关的移位和位运算相关的，为此我暂且归为一类来整理学习，这也为后续遇到同等问题可以提供解法和思路。

当前文章基于jdk 1.8进心学习和测试。

一、判断一个整数是偶数还是奇数

题目很简单，就是判断一个整数是偶数还是奇数，整数可能是负数、零和正数。

解法一：

1 public static boolean iseven(int num) {
2     return num % 2 == 0 ? true : false;
3 }

注意，这种简单的算法其实是有个陷阱的，你只能按照上面这种方式来使用，不能够用【num % 2 == 1】这种方式来判断奇数然后剩下的就是偶数的方式，因为在java中，取模运算的规则是【a%b == a - (a / b) * b】，所以如果以取模判断奇数的话，那么输入-1的话，-1%2的结果却不是1，上面的等式就不成立，所以就会把-1误判为偶数，这样就错误了，所以这里提醒一下，不能使用模2的结果是否等于1来判断奇偶。

解法二：

因为奇数的二进制最后一位都是1，所以我们可以在此做文章，我们用1去与这个数，如果结果不是0，那就是奇数，否则为偶数，看下面代码：

1 public static boolean iseven(int num) {
2     return (num & 1) == 0 ? true : false;
3 }

二、输出该整数的二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

问题思路就是先从高位开始计算1的个数，然后把高位去掉，再计算剩余的，这里用与操作符，同1做&运算，最后剩下的是1。n&(n-1)的操作，能把n的最高位的1给去掉，以此来计数。

1 public static int countone(int num) {
2     int count = 0;
3     while(num != 0) {
4         num &= (num - 1);
5         count++;
6     }
7     return count;
8 }

三、输出该整数的二进制中0的个数

与上面的问题相似，也是用移位来操作，先比较最末尾的数是否为0，判断完成之后再整体右移一位，比较方法是&1的结果是否为0，为0则统计结果。

 1 public static int countzero(int num) {
 2     int count = 0;
 3     while(num != 0) {
 4         if((num & 1) == 0) {
 5             count++;
 6         }
 7         num >>>= 1;
 8     }
 9     return count;
10 }

四、判断一个整数是否是2的n次幂

这个题目也是当初我面试的时候遇到的，其实很简单，想一下2的n此幂的特征，就是1的n次左移位，在二进制数看来，这个数就是一个1后面带着一串0，很好处理，通过n&(n-1)的方式来处理，只要结果是0，那么此数就是2的n次幂。

1 public static boolean is2power(int num) {
2     return (num & (num - 1)) == 0 ? true : false;
3 }

五、输出一个整数的二进制高位连续0的个数。

将一个整数的二进制数中，将其高位连续为0的个数，比如整数28，在计算机中的二进制存储为0000, 0000, 0000, 0000, 0000, 0000, 0001, 0010，那么高位连续为0的个数为27个，写一个程序，输入这样一个整数，能够输出该数的高位连续为0的个数长度，比如输入18结果为27。

解法一：

移位计数，每次向右移位之后然后看此数是否为0，如果是则说明前面都是0了，然后通过每次移位计数来统计0的个数。

1 public static int getzeroslen(int num) {
2     int size = integer.size;
3     int count = 1;
4     while((num >>>= 1) != 0) {
5         count++;
6     }
7     return size - count;
8 }

解法二：

上面这种方法可行，但是复杂度就是o(size of integer)的大小了，其实在integer类中有个静态方法tobinarystring(int i)，这个方法就是将整数转换为二进制，而其调用了一个内部函数tounsignedstring0(int val, int shift)，这个函数有个numberofleadingzeros方法就是计算int变量的计算机二进制表示的高位连续0位的数量，我们可以通过这种方法来获得最高非0位到最高位的长度。

 1 public static int getzeroslen(int num) {
 2     if (num == 0)
 3         return 32;
 4     int n = 1;
 5     if (num >>> 16 == 0) { n += 16; num <<= 16; }
 6     if (num >>> 24 == 0) { n +=  8; num <<=  8; }
 7     if (num >>> 28 == 0) { n +=  4; num <<=  4; }
 8     if (num >>> 30 == 0) { n +=  2; num <<=  2; }
 9     n -= num >>> 31;
10     return n;
11 }

上面的代码也是通过移位，但是采用了分治思想，就是每次一半一半的移位，这也是得益于二进制数字的特性。先通过移动一半即右移16位再判断移动后数据是否等于0，为0的话说明高16位都是0，计数16，同时把低16位冲到高16位，即左移16位后面都补0，接着看高16位，同样采用分治法，先从一半开始看，16+16/2=24，移动14位再计算，以此类推，在最后剩下2位时，其实只需要看最高位了，因为一开始n赋值位，所以后面用他减去最高为即可，可以自己推理一下。

六、输出一个正整数的大于等于它的最近的2次幂的数

输出一个正整数的大于等于它的最近的2次幂的数，比如输入13，那么输出16，输入16则输出16.

我们这里可以学习hashmap源码中的算法，在其有参构造函数中，如果设定了初始容量，那么在hashmap初始化时会调用一个内部叫做tablesizefor的方法来计算离该数最近的二次幂来重设容量值，于是我们参照源码这样改写：

 1 public static int getnear2power(int num) {
 2     if(num <= 0) {
 3         return 0;
 4     }
 5     int n = num - 1;
 6     n |= n >>> 1;
 7     n |= n >>> 2;
 8     n |= n >>> 4;
 9     n |= n >>> 8;
10     n |= n >>> 16;
11     return n + 1;
12 }

这个算法的原理就是，先将这个值减去一，因为要考虑到本身就是2的n次幂的可能，然后再把这个数的二进制表示中，最高位为1的后面全部用1来补齐，补齐之后加一，自然就是最近的大于该数的2次幂的数了，也可以在稿纸上自行推演一番，算法着实巧妙。