移位和位运算相关算法题学习积累
最近逛博客发现几个很有意思的算法题,大都是二进制相关的移位和位运算相关的,为此我暂且归为一类来整理学习,这也为后续遇到同等问题可以提供解法和思路。
当前文章基于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次幂的数了,也可以在稿纸上自行推演一番,算法着实巧妙。