算法入门篇——用位运算解决一些问题

目录

1.判断一个数是2的次方数

2.统计一个数，它的二进制数中，1的个数

3.在2*（n-1）个数中，找到只出现一次的那个数

---

1.判断一个数是2的次方数

这个问题有好几种做法，但是最优雅的解法是用’位运算‘来做。

总所周知，一个2的次方数，其二进制必定是100....000，将其减1，就是0111....111，两者进行与

运算必定是0。

即a&(a-1)=0

代码如下：

public class 二的次方数 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while (sc.hasNext()) {int a = sc.nextInt();if ((a & (a - 1)) == 0) {System.out.println("是2的次方数");} else {System.out.println("不是2的次方数");}}}
}

2.统计一个数，它的二进制数中，1的个数

这个问题，也有很多思路，但是在这里，我们用位运算来做，还是用这个a&(a-1)来做，这个式子

有什么作用呢？

它就是把这个数的二进制数最右边的1置0

举个例子

1.末尾为1

a:    000001

a-1: 000000

相与后为：000000

2.末尾不为0

a:    001100

a-1: 001011

相与后为 001000

看见没，就是把最右边的1置0，只要它不等于0，继续进行这样的操作，即可，就能统计出1的个

数

代码：

public class 二进制中1的个数 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int a = sc.nextInt();int count = 0;while (a > 0) {a = a & (a - 1);count++;}System.out.println(count);}}
}

3.在2*（n-1）个数中，找到只出现一次的那个数

这里，我们使用异或运算，使用常规方法会出现很多问题。

因为

x^x=0    相同异或为0

x^0=x     与0异或 为原数

若测试数据为：1 2 3 2 3 4 4

按照交换律：2 2 3 3 4 4 1

前面相同的都异或为0，再与1异或，为1

代码：

public class 查找只出现一次的数 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = 0;int ans = 0;//记录结果int a=0;//每次读入的数while (sc.hasNext()) {ans=0;//每一次测试将结果置0n = sc.nextInt();for (int i = 0; i < 2 * n - 1; i++) {a=sc.nextInt();ans=ans^a;}System.out.println(ans);}}
}