欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-14 18:49:43
最近逛博客发现几个很有意思的算法题,大都是二进制相关的移位和位运算相关的,为此我暂且归为一类来整理学习,这也为后续遇到同等问题可以提供解法和思路。 当前文章基于JDK 1.8进心学习和测试。 一、判断一个整数是偶数还是奇数 题目很简单,就是判断一个整数是偶数还是奇数,整数可能是负数、零和正数。 解法 ......

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

当前文章基于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次幂的数了,也可以在稿纸上自行推演一番,算法着实巧妙。