目录

01位运算的奇巧淫技

位运算的简单应用

1.判断奇偶数：

2.获取二进制位是1还是0（两种解决方法）：

3.交换两个整数变量的值：

4.不用判断语句，求整数的绝对值：

位运算的例题

题1:找出唯一成对的数

题2:找出落单的那个数

题3:二进制中1的个数

题4:是不是2的整数次方

题5：将整数的奇偶位互换

题6：0~1间浮点实数的二进制表示

题7：出现k次与出现1次

---

 

01位运算的奇巧淫技

位运算的简单应用

1.判断奇偶数：

任何整数，如果是奇数，则转化为二进制数后，最后一位二进制位肯定为1，为偶数，则最后一位二进制位为0。利用这个性质，将任意整数x与1作与运算，如果结果为1，则x为奇数；结果为0，则x为0数。

示例代码：

public class Case1_JudjeOddEven { public static void main(String[] args) { int a = 40; int b = 31; judjeOddEven(a); judjeOddEven(b); } public static void judjeOddEven(int x) { System.out.println( ((x&1) == 0) ? (x + "是偶数！") : (x + "是奇数！") ); } } //------------------------------------------------------- // 运行结果： 40是偶数！ 31是奇数！

2.获取二进制位是1还是0（两种解决方法）：

方案1：做与运算。例如：判断x的第五位二进制是1还是0，可以与1<<4做与运算，然后将结果>>4位，判断最终结果是1还是0。如果最终结果是0，则x的第五位为0，否则第五位的二进制位1。

方案2：做与运算。例如：判断x的第五位二进制是1还是0，可以将x>>4位，与1做与运算，判断最终结果是1还是0。如果最终结果是0，则x的第五位为0，否则第五位的二进制位1。  

public class Case2_Judje0_1 { public static void main(String[] args) { judje0_1(10, 2); judje0_1(10, 3); judje0_1_2(10, 2); judje0_1_2(10, 3); } /** * 判断整数x的第y位的二进制位是0还是1 * @param x 一个整数x * @param y 判断x的二进制的第几位 */ //方案1代码 public static void judje0_1(int x ,int y) { System.out.println(x + "的第" + y + "位的二进制位为：" + ( ((x & (1<<(y-1)))>>(y-1)) == 0 ? "0":"1")); } //方案2代码 public static void judje0_1_2(int x ,int y) { System.out.println(x + "的第" + y + "位的二进制位为：" + ( ((x>>(y-1)) & 1) == 0 ? "0":"1")); } }

10的第2位的二进制位为：1

10的第3位的二进制位为：0

10的第2位的二进制位为：1

10的第3位的二进制位为：0

3.交换两个整数变量的值：

思路： 利用异或的性质实现。对于任何数x，都有x^x =0, x^0 = x， 同自己求异或为0，同0求异或为自己。 自反性：ABB = A^0=A,连续喝同一个因子做异或运算，最终结果为自己。如交换A、B的值，有：

A = A ^ B B = A ^ B （B = A ^ B ^ B = A） A = A ^ B   (A = A ^ A ^ B = B)

public class Case3_SwapValue { public static void main(String[] args) { int a = 3, b = 6; System.out.println("交换前：a=" + a + " b=" + b); a = a ^ b; b = a ^ b; a = a ^ b; System.out.println("交换后：a=" + a + " b=" + b); } }

交换前：a=3 b=6

交换后：a=6 b=3

4.不用判断语句，求整数的绝对值：

思路： 利用位运算的移位，异或运算实现。

原理：将一个整型整数x，带符号右移31位，则结果要么是0，要么是-1。其中如果是0，则x为正数，为-1则x为负数。然后，将x与右移31位后的结果做异或运算，当与x^0是，结果还是x。 当x^-1时，结果为x取反，即x的反码，然后+1，即为x的绝对值。  

位运算的例题

题1:找出唯一成对的数

题目： ​ 1-1000这1000个数放在10001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将他找出来；不用辅助存储空间，能否设计一个算法实现？

思路： 利用位运算异或的性质，AA=0;A0=A.

将1001个数一起做异或运算，会把相同的那组数去除。但是要找的数为相同的数，所以在和1-1000的每个数做异或，最后就能找到那个数。

java:

public class Case5_唯一成对的数 { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5}; int x = 0; //数组中每个数都互相进行异或运算。相同数会被消除 for(int i = 0; i < arr.length; i++) { x = x ^ arr[i]; } //再将异或运算结果与1-10所有数进行异或，就会消除所有不同的数，最后剩下唯一一个数。 for(int i = 1; i < arr.length; i++) { x = x ^ i; } System.out.println("数组中唯一重复的数是：" + x); } }

题2:找出落单的那个数

题目：

一个数组里除了某个数字之外，其他的数字都出现了两次。请写程序找出这个只出现了一次的数字。

和上题思路相同。利用异或，相同的数异或，会消去。

java:

public class solution { public static void main(String[] args) { int[] arr = {1, 7, 5, 3, 10, 6, 3, 6, 7, 8, 5, 10, 1}; int x = 0; for(int i = 0; i < arr.length; i++) { x = x ^ arr[i]; } System.out.println("落单的那个数是：" + x); } }

题3:二进制中1的个数

题目：

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。

例：9的二进制表示为1001，有2位是1.

思路：

解题方式有三种方式：与上面判断某位是1还是0思想相同。

方案1：与上面判断某位是1还是0思想相同。第一种方案是：例如：判断x的第五位二进制是1还是0，可以与1<<4做与运算，然后将结果>>4位，判断最终结果是1还是0。如果最终结果是0，则x的第五位为0，否则第五位的二进制位1。然后循环判断每个二进制位。

方案2：做与运算。例如：判断x的第五位二进制是1还是0，可以将x>>4位，与1做与运算，判断最终结果是1还是0。如果最终结果是0，则x的第五位为0，否则第五位的二进制位1。

方案3：（x-1）& x，利用该式可循环消去低位的1，循环了多少次，就有多少个1。原理：

例如9：二进制位1001 1001 //x - 1 //x-1 --------- 1000 //消去了低位的1 & 1001 //(x-1) & x --------- 1000 //新的x - 1 --------- 0111 & 1000 // (x-1) & x --------- 0000 //消去了最后一个1. // 循环多少次则该数的二进制有多少个1 public class 二进制中1的个数 { public static void main(String[] args) { int x = 2352; // 输出x的二进制位，作为验证。 System.out.println(Integer.toBinaryString(x)); // 方案1 int count = 0; //初始化，用来记录1的个数 for(int i = 0; i < 32; i++) { if(((x&(1<<i))>>i) == 1) { count++; } } System.out.println(count); // 方案2 count = 0; //初始化，用来记录1的个数 for(int i = 0; i < 32; i++) { if(((x>>i) & 1) == 1) { count++; } } System.out.println(count); // 方案3 count = 0; while(x != 0) { x = ((x-1) & x); count++; } System.out.println(count); } }

题4:是不是2的整数次方

题目：

用一条语句判断一个整数是不是2的整数次方。

方法：

转化为二进制问题：是否只有一个1，例如001000,0100000等，这种数就是2的整次方数，聪明如你，已经看出利用上面的第三种方法的原理就可以解决这个问题。（不考虑负整数次方）

public class 是不是2的整数次方 { public static void main(String[] args) { is2(1024); is2(1000); } public static void is2(int x){ if(((x-1) & x) == 0) { System.out.println(x + "是2的整数次方！"); }else { System.out.println(x + "不是2的整数次方！"); } } }

题5：将整数的奇偶位互换

题目：

将一个整数的二进制位上的1与0做交换。

思路：利用了&和^的结合，上一篇笔记讲过^的作用是：0作^保留，1作^取反。可以借助辅助空间，将十进制先转化为二进制，再令奇偶位互换。当然这章主要是利用位运算，那么就一定有简单的方法，主要思路是先保留奇数位再保留偶数位，通过移位再异或，将奇偶位互换。

//例如：求10,交换后的数。 10的二进制为：1010 1010 & 01010101 01010101 01010101 01010101 --------------------------------------- x 0000 //保留奇数位上的数 1010 & 10101010 10101010 10101010 10101010 --------------------------------------- y 1010 //保留偶数位上的数 (x<<1) ^ (y>>1) = (0000<<1) ^ (1010>>1) = 0000 ^ 0101 = 0101 //从而实现了，奇偶位互换

代码：

public class 将整数奇偶位互换 { public static void main(String[] args) { int n = 10; System.out.println(Integer.toBinaryString(n)); int a = swapOddEven(n); System.out.println("10的二进制位交换后变为" + a); System.out.println(Integer.toBinaryString(a)); } public static int swapOddEven(int n) { //消除奇数位，保留偶数位 //和01010101 01010101 01010101 01010101做运算 int x = n & 0x55555555; //消除偶数位，保留奇数位 //和10101010 10101010 10101010 10101010做运算 int y = n & 0xaaaaaaaa; return (x<<1)^(y>>1); } }

题6：0~1间浮点实数的二进制表示

题目： 给定一个介于0和1之间的实数，如（0.625），类型为double，打印它的二进制表示（0.101，因为小数点后的二进制分别表示为0.5 , 0.25, 0.125…)

如果该数字无法精确的用32位以内的二进制表示，则打印“ERROR”。

思路： 可以每次讲x * 2，然后去整数部分，如果整数部分为1，则在二进制表示在0. 后面加1，如果为0，则加0. 循环，直到x为0结束。

代码示例：

java：

public class 浮点实数的二进制表示 { public static void main(String[] args) { double x = 0.625; StringBuffer sb = new StringBuffer("0."); while(x > 0) { // 乘2: 挪整 double r = x * 2; //判断整数部分 if (r >= 1) { sb.append("1"); // 消除掉整数部分 x = r - 1; }else{ sb.append("0"); x = r; } if(sb.length() > 34) { System.out.println("ERROR"); return; } } System.out.println(sb.toString()); } }

c++：

/*二进制小数*/ #include <iostream> #include <iomanip> #include <stdio.h> #include <stdlib.h> #include <cstring> using namespace std; int main() { double num; string binary; binary.append("0."); cin >> num; int i; while(num > 0){ //乘2 double r = num*2; //判断整数部分 if(r >= 1){ //如果存在个位进位问题 binary.append("1"); //消除整数部分 num = r - 1; } else{ //如果不存在个位进位问题 binary.append("0"); num = r; } if(binary.length()>34){ //0.不算入32位中 cout << "ERROR" << endl; return 0; } } cout << binary << endl; return 0; }

题7：出现k次与出现1次

题目： 数组中只有一个数出现了1次，其他的数都出现了K次，请输出只出现了一次的数。

思路： 2个相同的2进制数做不进位加法，结果为0.

10个相同的10进制数做不进位加法，结果为0.

k个相同的k进制数做不进位加法，结果为0.

解题方式：做k进制的不进位加。

代码示例： java：

public class 出现K次 { public static void main(String[] args) { //假设K=3时的解题方法 int[] arr = {2, 2, 2, 9, 7, 7, 7, 3, 3, 3, 6, 6, 6, 0, 0, 0}; int len = arr.length; // 存取每个数的三进制 char[][] kRadix = new char[len][]; int k = 3; //转化k进制字符数组 //记录转化三进制后最长的长度 int maxlen = 0; //对于每个数字 for(int i = 0; i < len; i++) { kRadix[i] = new StringBuffer(Integer.toString(arr[i], k)).reverse().toString().toCharArray(); if(kRadix[i].length > maxlen) maxlen = kRadix[i].length; } int[] resArr = new int[maxlen]; for(int i = 0; i < len; i++) { // 不进位加法 for(int j = 0; j < maxlen; j++) { if(j >= kRadix[i].length) resArr[j] += 0; else resArr[j] += (kRadix[i][j] - '0'); } } int res = 0; for(int i = 0; i < maxlen; i++) { res += (resArr[i] % k) * (int)(Math.pow(k, i)); } System.out.println(res); } }

c++：参考：https://blog.csdn.net/OpenStack_/article/details/88199238

#include<iostream> #include<algorithm> //#include<cmath> using namespace std; //十进制数转K进制 string decTok(int dec,int k){ string ret=""; //作为结果 while(dec>0){ ret+=char(dec%k+'0'); //如：5+'0'='5' dec/=k; } reverse(ret.begin(),ret.end()); return ret; } //K进制转十进制 int kTodec(string str,int k){ int ans=0; for(int i=0;i<str.size();i++){ ans=ans*k+(str[i]-'0'); //020 首位是最高位 //ans+=(str[i]-'0')*pow(k,str.size()-1-i); } return ans; } int main(){ int n[]={1,1,1,3,3,3,5,5,5,9,9,9,6,7,7,7}; int k=3; string str[16]; for(int i=0;i<16;i++){ str[i]=decTok(n[i],k); } //找出16条字符串中最大长度 int maxlen=0; int len; for(int i=0;i<16;i++){ len=str[i].size(); maxlen=max(maxlen,len); //不能用： maxlen=max(maxlen,str[i].size()) } //16条字符串中，若字符串长度<maxlen，则进行补齐，以便逐位做不进位加 for(int i=0;i<16;i++){ while(str[i].size()<maxlen){ str[i]="0"+str[i]; } } //ans:结果。初始化 string ans=""; while(ans.size()<maxlen){ ans+="0"; } //16条字符串做不进位加 for(int i=0;i<16;i++){ for(int j=0;j<maxlen;j++){ ans[j]=char(((str[i][j]-'0')+(ans[j]-'0'))%k+'0'); } } cout<<ans<<endl; //ans字符串结果转为10进制数 int finalans=kTodec(ans,k); cout<<finalans<<endl; return 0; } #include <iostream> #include <algorithm> #include <string> using namespace std; /*十进制转换*/ string intToA (int n, int radix) //进制 { string ans = ""; do { int t = n %radix; if(t >= 0 && t <= 9) ans += t+'0'; else ans = t-10 + 'a'; n /= radix; }while(n != 0); //这里可以防止输入为0的情况。 reverse(ans.begin(),ans.end()); return ans; } //K进制转十进制 int kTodec(string str,int k){ int ans=0; for(int i=0;i<str.size();i++){ ans=ans*k+(str[i]-'0'); //020 首位是最高位 //ans+=(str[i]-'0')*pow(k,str.size()-1-i); } return ans; } int main() { int k = 3; //出现了3次 int arr[10] = {1,1,1,2,2,2,3,3,3,9}; string str[10]; //将其转换为k进制 for(int i = 0 ; i < 10; ++i ) { str[i] = intToA(arr[i] , k); cout << str[i] << endl; } cout << endl; //主要是为了补位 //找出16条字符串中最大长度 int maxlen=0; int len; for(int i=0;i<10;i++){ len=str[i].size(); maxlen=max(maxlen,len); //不能用： maxlen=max(maxlen,str[i].size()) } //16条字符串中，若字符串长度<maxlen，则进行补齐，以便逐位做不进位加 for(int i=0;i<10;i++){ while(str[i].size()<maxlen){ str[i]="0"+str[i]; } } //ans:结果。初始化 string ans=""; while(ans.size()<maxlen){ ans+="0"; } //不进位加法 for(int i=0;i<10;i++){ for(int j=0;j<maxlen;j++){ ans[j]=char(((str[i][j]-'0')+(ans[j]-'0'))%k+'0'); } } cout<<ans<<endl; //ans字符串结果转为10进制数 int finalans=kTodec(ans,k); cout<<finalans<<endl; return 0; }

几道习题：https://blog.csdn.net/qq_27901917/article/details/87609966