位运算

---

一、原码、反码、补码

原码：符号位（正数为0、负数为1）+二进制数
反码：正数的反码=正数的原码；负数的反码=负数的原码除符号位外按位求反
补码：正数的补码=正数的反码；负数的补码=负数的反码+1

整数	原码	  反码	补码
+7	 0111	0111	0111
-7	 1111	1000	1001

---

二、与（&）、或（|）、异或（^）

1&1=1，1|1=1
1&0=0，1|0=1
0&1=0，0|1=1
0&0=0，0|0=0
1 ^ 1=0，1 ^ 0=1
0 ^ 1=1，0 ^ 0=0
x ^ x=0，x ^ 0=x
a ^ b ^ c=a ^ c ^ b=b ^ c ^ a

例如：

7&3= 111 & 011 =011=3
7|3= 111 | 011 =111=7
7 ^ 3=111 ^ 011 =100=4

---

三、移位运算

①7<<2

7的补码：0000 0111
向左移两位：0001 1100
$$
7<<n=7 * 2^{n}
$$

②7>>2

7的补码：0000 0111
向右移两位：0000 0001
$$
7>>2=7 / 2^{2}=7 / 4=1
$$

③-7<<2

-7的补码：1111 1001
向左移两位：1110 0100

​ -7<<2=-28

④-7>>2

-7的补码：1111 1001
向右移两位：1111 1110

​ -7>>2=-2

注意！！！正数向下取证，负数向绝对值上取证

---

四，例题

题目一：

题目介绍：

输入一个正整数n，判断n是否为2的k次方，如果是，输出yes，否则输出no

思路分析：

$$
\begin{array}{l}4=2^{2} ， \text { 二进制为 } 100 \ 8=2^{3} ， \text { 二进制为 } 1000 \ 16=2^{4} ， \text { 二进制为 } 10000\end{array}
$$

将正整数n转成二进制，判断其是否为1开头，后面全0
或者：8→1000；7→0111；8&7=1000&0111=0000=0
即：n&(n-1)==0?“yes”:“no” 7 & 6= 0111 & 0110 = 0110 = 6

代码：

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println((n & (n - 1)) == 0 ? "yes" : "no");
		}
	}

}

---

题目二：

题目介绍：

输入一个十进制正整数n，输出n的二进制中1的个数。

思路分析 ：

n&(n-1)：把n的二进制最右边的1置为0（这是n&n-1的本质）
举个栗子：
7 & 6= 0111 & 0110 = 0110 = 6
6 & 5= 0110 & 0101 = 0100 = 4
4 & 3= 0100 & 0011 = 0000 = 0

程序代码：

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {
			int n = sc.nextInt();
			int count = 0;
			while (n > 0) {
				n = n & (n - 1);
				count++;
			}
			System.out.println(count);
		}
	}

}

---

题目三：

题目介绍：

在新年晚会上，每个人都会得到一份“特别的礼物”。现在轮到你去领取你的特殊礼物了，许多礼物现在放在桌子上，其中只有一件是你的。每一份礼物上都有一个卡片号码，你的卡片号码将与其他所有礼物不同，你可以假设只有一个数字出现奇数次。例如，现在有5个，他们的卡号是1、2、3、2、1。所以你的礼物将是卡号为3的那个，因为3是不同于所有其他数字的数字。

样例输入：

5
1 1 3 2 2
3
1 2 1
0

样例输出：

3
2

思路分析：

使用异或位运算
例：1 ^ 2 ^ 3 ^ 2 ^ 1 ^ 4 ^ 4= 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 4 ^ 4 ^ 3=0 ^ 0 ^ 0 ^ 0 ^ 3=0 ^ 3=3

程序代码：

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {
//			int n = sc.nextInt();
//			int[]arr=new int[n];
//			int ans=0;
//			for (int i = 0; i < arr.length; i++) {
//				arr[i]=sc.nextInt();
//				ans=ans^arr[i];
//			}
//			System.out.println(ans);			

//			上述方法太浪费空间了
			int n = sc.nextInt();
			int ans = 0;
			for (int i = 0; i < n; i++) {

				ans = ans ^ sc.nextInt();
			}
			System.out.println(ans);
//			这样子刚刚好
		}
	}
}