冲天香阵透长安，满城尽带黄金甲。这篇文章主要讲述算法 | 第5章 位操作相关《程序员面试金典》#yyds干货盘点#相关的知识，希望能为你提供帮助。
@[TOC](第5章 位操作相关《程序员面试金典》)
前言本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；
0. *经验总结 0.1 程序员面试金典 P94

• 位操作是优化代码的一种技巧；
• 一些操作技巧：（1s和0s表示一串1和0）
  
  • 乘2：左移1位；
  • 异或^：同0异1；
  • 某数与111100做与& 运算：将某数最后2位清零；

  异或	与	或
  x ^ 0s = s	x & 0s = 0	x | 0s = x
  x ^ 1s = ~x	x & 1s = x	x | 1s = 1s
  x ^ x = 0	x & x = x	x | x = x

  • 根据正数求复数：所有取反加1，符号位变为1；
  • 逻辑右移与算数右移：对于数 1 0110101（-75）；
  • 逻辑右移 > > > ：移位后 0 1011010（90），最终得到0；
  • 算数右移> > ：移位后 1 1011010（-38），最终得到-1；

0.2 java中的位运算相关代码 1. 算数移位
2. 逻辑移位

boolean getBit(int num, int i) return ((num & (1 < < i)) != 0);

4. 设置数位
5. 清零数位
清零第i位：

int clearBit(int num, int i) int mask = ~(1 < < i); return num & mask;

清零最高位到第i位（包括最高和第i位）：

int clearBitMSBthroughI(int num, int i) int mask = (1 < < i) - 1; return num & mask;

清零第i位到第0位（包括第i位和第0位）：

int clearBitsIthrough0(int num, int i) int mask = (-1 < < (i+1)); return num & mask;

6. 更新数位

int updateBit(int num, int i, boolean bitIs1) int value = https://www.songbingjia.com/android/bitIs1 ? 1 : 0; int mask = ~(1 < < i); return (num & mask) | (value < < i);

0.3 Java判断double是否为整数的方法Math.abs(num - (int)num) & lt; 0.000001
0.4Java进制转换API

• Integer类的静态方法：
• static String toBinaryString(int i)：返回数字i的二进制数字符串；
• static String toOctalString(int i)：返回数字i的八进制数字符串；
• static String toHexString(int i)：返回数字i的十六进制数字符串；
• static int parseInt(String s)： 将字符串参数s解析为带符号的十进制整数；
• static int parseInt(String s, int radix)： 将整数字符串s（radix用来指明s是几进制）转换成10进制的整数；

0.5 Math类常用API

• static double abs(double a)：返回double值的绝对值；
• static double ceil(double a)：向上取整，返回大于等于参数的最小的整数；
• static double floor(double a)：向下取整，返回小于等于参数最大的整数；
• static long round(double a)：返回最接近参数的long；(相当于四舍五入方法)
• static int max(int a, int b) ：返回a与b中较大值；
• static int min(int a, int b)：返回a与b中较小值；
• static double log10(double a)：返回 double值的基数10对数；
• static double pow(double a, doubl b) ：a^b；
• static double sqrt(double a) ：返回 double值的正确舍入正平方根；

0.6 位操作技巧（重要）

普通写法	位运算	含义
n == 1	in & 1	判断n是否为1
	n = n & (n-1)	将最低位的1清零
n == Math.pow(2, x)	(n & (n-1)) == 0	判断n是否为2的x次方

0.7 Java运算优先级
文章图片

0.8 Java中常用基本类型的取值范围

常用类型	多少字节	范围
byte	1*8=8 bit	-2^8^ ~ 2^7^(-128 ~ 127)
short	2*8=16 bit	-2^16^ ~ 2^15^(-32768 ~ 32767)
int	4*8=32 bit	-2^32^ ~ 2^31^(-2147483648 ~ 2147483647)
long	8*8=64 bit	-2^64^ ~ 2^63^(-18446744073709551616 ~ 18446744073709551615)
float	4*8=32 bit	-2^32^ ~ 2^31^(-2147483648 ~ 2147483647)
double	8*8=64 bit	-2^64^ ~ 2^63^(-18446744073709551616 ~ 18446744073709551615)
char	2*8=16 bit
boolean	8 bit	true / false

0.9 特殊二进制

十六进制	二进制	说明
0xaaaaaaaa	10101010101010101010101010101010	偶数位为1，奇数位为0
0x55555555	1010101010101010101010101010101	偶数位为0，奇数位为1
0x33333333	110011001100110011001100110011	1和0每隔两位交替出现
0xcccccccc	11001100110011001100110011001100	0和1每隔两位交替出现
0x0f0f0f0f	00001111000011110000111100001111	1和0每隔四位交替出现
0xf0f0f0f0	11110000111100001111000011110000	0和1每隔四位交替出现

1. 插入 [easy]
文章图片

1.1 考虑点

• 解决多位操作的问题时，需要进行测试，否则很容易犯下差一位的错误；

1.2 解法 1.2.1 位运算（优）

public int insertBits(int N, int M, int i, int j) int mask = ~(((int)Math.pow(2, j-i+1)-1)< < i); int m = M< < i; int result = (N & mask); return result | m;

• 执行时间：100.00%；内存消耗：95.99%；

2. 二进制数转字符串 [medium]
文章图片

2.1 考虑点

• 注意准备好测试用例；

2.2 解法 2.2.1 count计数法

public String printBin(double num) int count = 0; boolean isFind = false; while(count < = 30 & & !isFind) num*=2; count++; if(Math.abs(num - (int)num) < 0.000001) isFind = true; if(isFind) StringBuilder sb = new StringBuilder(); sb.append("0."); //这里注意不要写成 sb.append(0.) int n = (int)num; while(n != 0) n/=2; count--; for(int i = 0; i < count; i++) sb.append(0); sb.append( Integer.toBinaryString( (int)num) ); return sb.toString(); else return "ERROR";

• 执行时间：100.00%；内存消耗：45.18%；
• 统计需要乘多少个2才变成整数，减去转成二进制后的位数，得有效位0的数量；

2.2.2 折半比较法（优）

public String printBin(double num) String str = "0."; double i = 0.5; while(str.length() < 32) if(num-i > = 0) str += "1"; num = num - i; else str += "0"; if(num == 0) return str; i /= 2; return "ERROR";

• 执行时间：100.00%；内存消耗：97.48%；
• num逐个减去 2^-1、^2^-2^、2^-3^……减法成功则为添1，否则添0；

3. 翻转数位 [easy]
文章图片

3.1 考虑点

• 注意num为负数的情况，num=-1时，其二进制数为32个1；

3.2 解法 3.2.1 逐个遍历法

public int reverseBits(int num) //注意num为-1的情况 if(num == -1) return 32; String binaryString = Integer.toBinaryString(num); int a = 0; int b = 0; int max = 0; int count = 0; for(int i = 0; i < binaryString.length(); i++) if(binaryString.charAt(i) == 0) a = b; b = count; count = 0; if(a+b > max) max = a+b; else count++; //最后一位不为0时，count的数出不来； if(count != 0) max = Math.max(b+count, max); return max+1;

• 执行时间：100.00%；内存消耗：61.13%；
• 时间复杂度：O(n)，n为整数的位数；注意需要跟面试官说明n的含义，不然有可能会有歧义；
• 空间复杂度：O(1)；
• 需要注意最后一位不为0的情况与num为负数的情况；

3.2.2 滑动窗口法（优）

public int reverseBits(int num) int max = 0; int count = 0; boolean flag = false; int start = 0; for (int i = 31; i > = 0; i--) int i1 = (num > > i) & 1; if (i1 == 1) count++; max = Math.max(max, count); else if (!flag) count++; flag = true; start = i; max = Math.max(max, count); else count = 0; i = start; flag = false; return max;

• 执行时间：100.00%；内存消耗：99.05%；

4. 下一个数 [medium]
文章图片

4.1 考虑点

• 注意特殊值，两个边界范围；
• 注意移位方向；

4.2 解法 4.2.1 位运算法（优）

public int[] findClosedNumbers(int num) if(num == 1) return new int[]2,-1; if(num == 2147483647)//注意特殊值 return new int[]-1,-1; //较大：从右往左遍历，找到遇到1后的一个0（期间统计1的个数count1），交换0和1。 //如果n不为1，需要把其余1后移；如果n为1，不做处理； boolean isFound0 = false; int count1 = 0; int i = 0; while(!isFound0) if(count1 != 0 & & ((num > > i) & 1) == 0) //注意加括号，不然优先级不够 isFound0 = true; if(((num > > i) & 1) == 1) count1++; i++; int moreNum = 0; if(count1 == 1) moreNum = num > > (i-1); moreNum++; moreNum = moreNum < < (i-1); else moreNum = num > > i-1; moreNum++; moreNum = moreNum < < (i-count1); for(int k = 0; k < count1-1; k++) moreNum = moreNum < < 1; moreNum++; //较小：从右往左遍历，找到第一个1（统计期间0的个数count0）。 //如果m不为0，则该1退一位；反之，遍历到有0后的第一个1，该1退位，后面1补上接着； boolean isFound1 = false; int count0 = 0; int j = 0; while(!isFound1) if(((num > > j) & 1) == 1) isFound1 = true; else count0++; j++; int lessNum = 0; if(count0 == 0) isFound0 = false; isFound1 = false; count1 = 1; while(!isFound0) if(((num > > j) & 1) == 0) isFound0 = true; else count1++; j++; while(!isFound1) if(((num > > j) & 1) == 1) count1++; isFound1 = true; j++; lessNum = num > > j; lessNum = lessNum < < 1; for(int k = 0; k < count1; k++) lessNum = lessNum < < 1; lessNum++; j--; lessNum = lessNum < < (j-1); else lessNum = num > > j; //注意方向 lessNum = lessNum < < 2; lessNum++; lessNum = lessNum < < (j-2); return new int[]moreNum, lessNum;

• 执行时间：100.00%；内存消耗：89.61%；

4.2.2 暴力穷举法

public int[] findClosedNumbers(int num) if(num == 1) return new int[]2,-1; if(num == 2147483647)//注意特殊值 return new int[]-1,-1; int up = num + 1; //向上枚举 int down = num - 1; //向下枚举 int count = findOneCount(num); //num的1的个数 while (findOneCount(up) != count) up++; if (up < 0) //越界了那就是找不到，设置为-1 up = -1; break; while (findOneCount(down) != count) down--; if (down < 0) //变为负数了那就是找不到了，设置为-1 down = -1; break; return new int[]up, down; //求数的二进制1的个数 private static int findOneCount(int num) int count = 0; while (num != 0) num & = num - 1; count++; return count;

• 执行时间：100.00%；内存消耗：55.20%；

4.2.3 看不懂啥方法

public int[] findClosedNumbers(int num) int mx = nextOne(num), mi = ~nextOne(~num); return new int[]mx > 0 ? mx : -1, mi > 0 ? mi : -1; public int nextOne(int x) long lowbit = x & (-x); long toZero = x + lowbit; return (int)((x & ~toZero) / lowbit > > 1 | toZero);

• 执行时间：100.00%；内存消耗：45.16%；
• 如果1的个数不同直接往低位加，这里要求相同，所以只能把最右边的连续1左移，然后保留连续1区间的最左一个，剩下的（连续长度-1）个的搬到全局最右边，步骤：
  • 1.先求出二进制最右边的1得到 lowbit = x & (-x)；
  • 2.求出最左1也就是消去连续1得到连续0 toZero = x + lowbit；
  • 3.把（最右连续1长度-1）个1搬到全局最优 (x & ~toZero) / lowbit > > 1；
  • ps: ~toZero 与 x 进行并得到最右连续1部分 /lowbit 后把1搬到右边 这里因为相加进位，所以要右移去掉一个1

6. 整数转换（汉明距离） [easy]
文章图片

6.1 考虑点

• 将最低位清零的写法n = n & (n-1)；

6.2 解法 6.2.1 异或遍历法（优）

//第一种写法 public int convertInteger(int A, int B) int C = A ^ B; int count = 0; for(int i = 0; i < 32; i++) if(((C > > i) & 1) == 1) count++; return count; //第二种写法 public int convertInteger(int A, int B) int count = 0; for(int C = A ^ B; C != 0; C = C > > > 1) count += C & 1; return count; //第三种写法（优） public int convertInteger(int A, int B) int count = 0; for(int C = A ^ B; C != 0; C = C & (C-1)) count++; return count;

• 执行时间：100.00%；内存消耗：12.36%；
• 先做异或操作，再遍历每一位统计1的个数；
• 第三种写法的c = c & (c-1)是清除最低位1；

7. 配对交换 [easy]
文章图片

7.1 考虑点

• 可以询问面试官需要处理的数据位数；

7.2 解法 7.2.1 隔位操作法

public int exchangeBits(int num) int moreNum = num < < 1; int lessNum = num > > 1; int result = lessNum; for(int i = 1; i < 31; i+=2) if(((moreNum > > i) & 1) != ((lessNum > > i) & 1)) result = change(result, i); return result; public int change(int lessNum, int i) int mask = ~(1 < < i); // i位清零 int result = lessNum & mask; if(result != lessNum) return result; else return (result | (1 < < i));

• 执行时间：100.00%；内存消耗：63.11%；

7.2.2 特殊二进制法（优）

public int exchangeBits(int num) //奇数 int odd = num & 0x55555555; //偶数 int even = num & 0xaaaaaaaa; odd = odd < < 1; even = even > > > 1; return odd | even; //简短写法 public int exchangeBits(int num) return ((num& 0x55555555) < < 1) | ((num& 0xaaaaaaaa) > > > 1);

• 执行时间：100.00%；内存消耗：48.19%；
• 分别取出奇数位和偶数位，移动后做或运算；
• 0x55555555 = 0b0101_0101_0101_0101_0101_0101_0101_0101
• 0xaaaaaaaa = 0b1010_1010_1010_1010_1010_1010_1010_1010
• 用这两个数做与运算，把奇数位和偶数位取出来。然后位左移奇数位，右移偶数位。再把奇数位和偶数位做或运算；
• 这里运用逻辑右移而不是算数右移是因为我们希望符号位被0填充；
• 上述代码实现的是32位整数，处理64位整数需要修改掩码；

8. 绘制直线 [medium]
文章图片

题目理解：

文章图片

8.1 考虑点

• 一个简单的做法是：用for循环迭代，从x1到x2，一路设定每个像素，但这样做太没劲，效率不高；
• 处理这个问题需要十分细心，其中有很多陷阱和特殊情况；比如需要考虑x1到x2出于同一个字节的情况；

8.2 解法 8.2.1 逐组分析法

public int[] drawLine(int length, int w, int x1, int x2, int y) int higth = length*32/w; //屏幕高度 int intNum = w/32; //一行有多少个int int[] result = new int[length]; int index = 0; //前面第0 ~ y-1行为0，y*intNum个0 //第y行输出数字，intNum个数字 //后面第y+1 ~ hight-1行开始为0，(hight-y-1)*intNum个0//对于数组，前面至下标(x1+y*w)/32-1为0；从下标(x2+y*w)/32+1开始到结尾为0；中间为数 //第一个数，下标为i int i = (x1+y*w)/32; int min = Math.min( ((x1 / 32 + 1) * 32 - x1), (x2-x1+1)); for (int j = 0; j < min; j++) result[i] = result[i] < < 1; result[i]++; if(min == x2-x1+1) result[i] = result[i] < < (32-x2-1); i++; //中间-1的个数numOne int numOne = 0; if(x2/32 != x1/32) numOne = x2/32 - x1/32 -1; if(numOne != 0) for(int j = i; j < numOne + i; j++) result[j] = -1; //最后一个数，下标为i+numOne i = i + numOne; if(i < length & & (x2-x1)/32 > 0) for (int j = 0; j < (x2 - (x2 / 32) * 32 + 1); j++) result[i] = result[i] < < 1; result[i]++; result[i] = result[i] < < (32 - x2 + (x2/32)*32 -1); if( (x2 - (x2/32)*32 + 1) == 32) result[i] = -1; return result;

• 执行时间：100.00%；内存消耗：67.24%；
• 需要注意大量细节，包括中间-1的个数numOne，以及考虑最后一个数可以跟以一个重合的情况(x2-x1)/32 & gt; 0；
• 过于复杂，思路相同的不同实现方法如下；

8.2.2 位运算（优）

public int[] drawLine(int length, int w, int x1, int x2, int y) int[] ans=new int[length]; int low=(y*w+x1)/32; int high=(y*w+x2)/32; for(int i=low; i< =high; i++) ans[i]=-1; ans[low]=ans[low]> > > x1%32; ans[high]=ans[high]& Integer.MIN_VALUE> > x2 % 32; return ans;

• 执行时间：100.00%；内存消耗：51.73%；

最后::: hljs-center
新人制作，如有错误，欢迎指出，感激不尽！
:::
::: hljs-center
欢迎关注公众号，会分享一些更日常的东西！
:::
::: hljs-center
如需转载，请标注出处！
:::
【算法 | 第5章 位操作相关《程序员面试金典》#yyds干货盘点#】::: hljs-center

文章图片

:::

推荐阅读

• 

  网上商店数据分析
• 

  轻松解决常见问题 联想li6500清除错误的方法大全
• 

  中小学生学籍管理系统 中小学生学籍人籍分离如何处理，全国中小学生学籍查询
• 

  想做自媒体,怎么快速入门？
• 

  《万亿级流量转发|《万亿级流量转发 - BFE核心技术与实现》开始预售
• 

  地黄瓜种植时间方法
• 

  火影血继限定什么意思
• 

  全自动洗衣机不脱水显示e2怎么办,其实很简单
• 

  出师表文言文的翻译及原文 出师表文言文的翻译及原文注释
• 

  遇到西门子洗衣机水洗不起怎么办？3个处理方法帮助你
• 

  车位比1:1.3有必要买吗
• 

  易语言返回数据给php 易语言返回值
• 

  新生儿鼻塞怎么办？
• 

  系统分析师 难考吗
• 

  第五人格开启麦克风选项 第五人格可以开麦吗
• 

  绿豆芽怎么处理 凉皮的绿豆芽怎么处理
• 

  莱西高铁站有几个
• 

  糖醋松鼠鱼是哪里的菜 糖醋松鼠鱼是什么地方的菜
• 

  如何泡方便面更好吃
• 

  金盏花茶 金盏花茶什么人不能喝

• #yyds干货盘点# MySQL性能优化（为什么查询速度这么慢）
• 通过Citrix DDC服务器执行虚拟机快照
• #yyds干货盘点#醒酒菜（动画图解核心内存区--堆）
• shell条件测试if和case语句
• proc – 虚拟文件系统#yyds干货盘点#
• CentOS7常用技巧
• kubernetes-pod资源需求和资源限制
• 呕心沥血一个月，为小白新手准备的C/C++ Linux求职版学习路线
• shell脚本条件语句练习