位运算简介

位运算简介：

​ 程序中的所有数在计算机内存中都是以二进制的形式 储存 的。位运算就是直接对整数在内存中的二进制位进行 操作 。比如，and运算本来是一个逻辑 运算符 ，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）。

位运算的特点：

• 在处理 整形数值 时，可以直接对组成整形数值的各个位进行操作。这意味着可以使用屏蔽技术获得整个数中的各个位。
• &（与）、|（或）、^(异或)、~（非/取反）
• >>和<<运算符将二进制位进行右移或者左移操作。
• >>>运算符将用0填充高位；>>运算符用符号位填充高位，没有\<<<运算符。
• 对于int型，1<<35与1<<3是相同的，而左边的操作数是long型是需要对右侧的操作数作数模64。
• 与：相同为1，或：有一个为1结果为1，异或：相同为0，不同为1.

位运算的规则：



图：位运算的规则

异或的性质：

异或，可以理解为不进位的加法：1+1=0； 0+0=0；1+0=1

• 交换律：可任意交换运算因子的位置，结果不变。
• 结合律：即（a^b）^c == a^(b^c)
• 对于任何数x，都有x^x =0, x^0 = x， 同自己求异或为0，同0求异或为自己。
• 自反性：A^B^B = A^0=A,连续喝同一个因子做异或运算，最终结果为自己。

位运算的简单应用

判断奇偶数：

思路：

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

示例代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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是奇数！

获取二进制位是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。

  代码示例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  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")); } }

  程序运行结果：

  1 2 3 4

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

  交换两个整数变量的值：

  思路：

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

  A = A ^ B

  B = A ^ B （B = A ^ B ^ B = A）

  A = A ^ B (A = A ^ A ^ B = B)

  代码示例：

  1 2 3 4 5 6 7 8 9 10 11

  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); } }

  运行结果：

  1 2	交换前：a=3 b=6 交换后：a=6 b=3

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

  思路：

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

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

  代码示例：

  1 2

  程序运行结果：

  1 2	31的绝对值是：31 -21的绝对值是：21

  位运算的例题

  题1_找出唯一成对的数：

  题目：

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

  利用位运算异或的性质，A^A=0;A^0=A.

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

  代码实现：

  为了方便查看结果，测试用了1-10，有一个数重复。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  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); } }

  程序运算结果：

  1	数组中唯一重复的数是：5

  题2_找出落单的那个数：

  题目：

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

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

  示例代码：

  1 2 3 4 5 6 7 8 9 10

  public class 找出落单的那个数 { 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); } }

  程序运行结果：

  1

  落单的那个数是：8

  题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。原理：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  > 例如9：二进制位1001 > 1001 //x > - 1 //x-1 > --------- > 1000 //消去了低位的1 > & 1001 //(x-1) & x > --------- > 1000 //新的x > - 1 > --------- > 0111 > & 1000 // (x-1) & x > --------- > 0000 //消去了最后一个1. > // 循环多少次则该数的二进制有多少个1 >

  代码示例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

  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); } }

  程序运行结果：

  1 2 3 4

  100100110000 4 4 4

  题4_是不是2的整数次方：

  题目：

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

  思路为上题的方案3.

  代码示例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  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的整数次方！"); } } }

  程序运行结果：

  1 2	1024是2的整数次方！ 1000不是2的整数次方！

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

  题目：

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

  利用位运算的异或运算和与运算。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  > //例如：求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 //从而实现了，奇偶位互换 >

  代码示例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  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); } }

  程序运行结果：

  1 2 3

  1010 10的二进制位交换后变为5 101

  题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结束。

  代码示例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  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()); } }

  程序运行结果：

  1

  0.101

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

  题目：

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

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

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

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

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

  代码示例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

  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); } }

  程序运行结果：

  1. 1. 位运算简介
     1. 1.1. 位运算简介：
     2. 1.2. 位运算的特点：
     3. 1.3. 位运算的规则：
  2. 2. 位运算的简单应用
     1. 2.1. 判断奇偶数：
        1. 2.1.1. 思路：
        2. 2.1.2. 示例代码：
     2. 2.2. 获取二进制位是1还是0（两种解决方法）：
        1. 2.2.1. 思路：
        2. 2.2.2. 代码示例：
     3. 2.3. 交换两个整数变量的值：
        1. 2.3.1. 思路：
        2. 2.3.2. 代码示例：
     4. 2.4. 不用判断语句，求整数的绝对值：
        1. 2.4.1. 思路：
        2. 2.4.2. 代码示例：
  3. 3. 位运算的例题
     1. 3.1. 题1_找出唯一成对的数：
        1. 3.1.1. 题目：
        2. 3.1.2. 思路：
        3. 3.1.3. 代码实现：
     2. 3.2. 题2_找出落单的那个数：
        1. 3.2.1. 题目：
        2. 3.2.2. 思路：
        3. 3.2.3. 示例代码：
     3. 3.3. 题3_二进制中1的个数：
        1. 3.3.1. 题目：
        2. 3.3.2. 思路：
        3. 3.3.3. 代码示例：
     4. 3.4. 题4_是不是2的整数次方：
        1. 3.4.1. 题目：
        2. 3.4.2. 思路：
        3. 3.4.3. 代码示例：
     5. 3.5. 题5_将整数的奇偶位互换：
        1. 3.5.1. 题目：
        2. 3.5.2. 思路：
        3. 3.5.3. 代码示例：
     6. 3.6. 题6_0~1间浮点实数的二进制表示：
        1. 3.6.1. 题目：
        2. 3.6.2. 思路：
        3. 3.6.3. 代码示例：
     7. 3.7. 题7_出现k次与出现1次：
        1. 3.7.1. 题目：
        2. 3.7.2. 思路：
        3. 3.7.3. 代码示例：