位运算——基础练习

算法题

  Java 代码实现：

 1. 找出唯一成对的数

 2. 找出落单的那个数

 3. 二进制中 1 的个数

 4. 是不是 2 的整数次方

 5. 将整数二进制的奇偶位互换

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

 7. 出现 K 次与出现 1 次

1、找出唯一成对的数

题目：

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

解法：

  题目要求不使用辅助存储空间，所以不能再开辟数组进行计数。按位异或 (^)相同为 0，不同为 1，如果将这 1001 个数与 1-1000 的数按位异或则可以得到重复的元素值。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // 这里用1-10数举例，数组长度为11
        int[] array = {10, 1, 6, 8, 7, 4, 9, 3, 2, 7, 5};
        int x = 0;
        // 节约时间合并成一个循环
        for (int i = 1; i <= array.length; i++) {
            x = x ^ i ^ array[i - 1];
        }
        // 因为合并成一个循环，多异或了一个数组的长度
        System.out.println("重复元素为：" + (x ^ array.length));
    }

  运行结果：

重复元素为：7

2、 找出落单的那个数

题目：

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

解法：

  该题和上一题思路一样，都可以使用按位异或 (^)来实现数字的去重。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // 这里用1-5数举例，数组长度为9
        int[] array = {1, 2, 4, 3, 4, 3, 5, 2, 5};
        int x = 0;
        // 相同的数异或等于0
        for (int value : array) {
            x = x ^ value;
        }
        System.out.println("非重复元素为：" + x);
    }

  运行结果：

非重复元素为：1

3、二进制中 1 的个数

题目：

  请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。
  例：9 的二进制表示为 1001，有 2 位是 1。

解法：

  为了统计一个数的二进制中 1 的个数，则将该整数的每一位和 1 进行按位与运算，如果该位运算后还为 1 则表示该位原来 1。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        int a = 99;
        // 用于统计1的个数
        int count = 0;
        // int类型是32位所以循环32次
        for (int i = 0; i < 32; i++) {
            // 将a中的每一位和1进行按位与运算，该位结果为1则为True
            if ((a & (1 << i)) == 1 << i) {
                count++;
            }
        }
        System.out.println(a + "的二进制为：" + Integer.toBinaryString(a) + "，其中1的个数为：" + count);
    }

  运行结果：

99的二进制为：1100011，其中1的个数为：4

4、是不是 2 的整数次方

题目：

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

解法：

  题目的重点在于整数次方，如果一个数是 2 的整数次方，那么这个数的二进制一定只有一个 1。如果这个数的二进制中只有一个 1，则该数减 1 后与原数按位与结果就为 0，否则该数不是 2 的整数次方。

代码实现：

  源码：

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

  运行结果：

8是2的整数次方

5、将整数二进制的奇偶位互换

题目：

  将整数二进制的奇偶位互换。

解法：

  实现二进制的奇偶位互换，首先将该整数的二进制分别与奇数位全为 1 的二进制数和偶数位全为 1 的二进制数进行按位与运算，得到该数奇数位和偶数位，分别将其左移和右移 1 位再进行按位异或运算得到结果，如图：

Java 代码实现：

  源码：

    public static void main(String[] args) {
        int a = 8888;
        // 该数的二进制
        System.out.println(a + "的二进制为：" + Integer.toBinaryString(a));
        // 奇数位全为1的二进制数
        int odd = 0b01010101010101010101010101010101;
        // 偶数位全为1的二进制数
        int even = 0b10101010101010101010101010101010;
        // a的奇数位
        odd = (a & odd) << 1;
        // a的偶数位
        even = (a & even) >> 1;
        System.out.println(a + "奇偶位互换后的二进制为：" + Integer.toBinaryString(odd ^ even));
    }

  运行结果：

8888的二进制为：10001010111000
8888奇偶位互换后的二进制为：1000101110100

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

题目：

  给定一个介于 0 和 1 之间的实数（如：0.625），类型为 double，打印它的二进制表示（0.101，因为小数点后的二进制分别表示 0.5，0.25，0.125……）。如果该数字无法精确的用 32 位以内的二进制表示，则打印“ERROP”。

解法：

  这道题最大的难点是如何将十进制小数转换为二进制。十进制小数转为二进制的方法是乘二取整，直到小数位为 0。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // a必须在0-1之间
        double a = 0.625;
        // 使用StringBuilder进行字符串拼接比String效率高
        StringBuilder x = new StringBuilder("0.");
        while (a > 0) {
            a = a * 2;
            if (a >= 1) {
                a = a - 1;
                x.append(1);
            } else {
                x.append(0);
            }
            // 小数精准到32位，0和.不算，所有长度要大于34
            if (x.length() > 34) {
                System.out.println("ERROP");
                return;
            }
        }
        System.out.println("二进制为：" + x);
    }

  运行结果：

二进制为：0.101

7、出现 K 次与出现 1 次

题目：

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

解法：

  由题意得知，有些数出现的是 K 次并不是偶数次，所以不能直接异或。如果开辟数组统计每一个数出现的次数的话非常耗时，所以需要其他办法。
  2 个相同的二进制做不进位加法，结果为 0。
  10 个相同的 10 进制做不进位加法，结果为 0。
  K 个相同的 K 进制做不进位加法，结果为 0。
  所以将 K 个数转换为 K 进制做不进位加法，这些出现 K 次的都为 0，只留下一个出现一次的数。
  不进位加法的实现：将 k 个整数转为 k 进制，将 k 进制的每一位相加，然后对 k 求余即可。

Java 代码实现：

  源码：

    public static void main(String[] args) {
        // 9出现一次，其他出现两次
        int[] array = {1, 2, 3, 4, 5, 6, 8, 7, 9, 1, 2, 3, 6, 5, 8, 7, 4};
        // 记录数组的长度
        int length = array.length;
        // 对应题中的k
        int k = 2;
        // 数组中的元素转为k进制后的最大长度
        int radixMaxLength = 0;
        // 存储数组中的元素转为k进制后的每一位的值
        char[][] radixArray = new char[length][];
        for (int i = 0; i < length; i++) {
            // 将数组中的所有数转为k进制，由于二进制是从右往左，所以需要先反转再转成字符数组
            radixArray[i] = new StringBuilder(Integer.toString(array[i], k)).reverse().toString().toCharArray();
            // 获取最长的k进制的长度
            if (radixArray[i].length > radixMaxLength) {
                radixMaxLength = radixArray[i].length;
            }
        }
        // 用于存储array数组中所有元素转为k进制后每一位上的和
        int[] redisSum = new int[radixMaxLength];
        for (int i = 0; i < length; i++) {
            // 将所有数的二进制对应位相加
            for (int j = 0; j < radixMaxLength; j++) {
                // 如果当前k进制累加完则结束当前循环
                if (radixArray[i].length <= j) {
                    break;
                } else {
                    // radixArray数组是char类型，redisSum是int类型，
                    // 如果直接转型的话是按ASCII表进行转码，所以需要减去0对应的ASCII值。
                    redisSum[j] += (radixArray[i][j] - '0');
                }
            }
        }
        // 出现一次的数
        int x = 0;
        for (int i = 0; i < radixMaxLength; i++) {
            // a[i] % k得到不进位加法的每一位的值（系数），然后系数*基数的权次幂
            x += (redisSum[i] % k) * (Math.pow(k, i));
        }
        System.out.println("非重复的元素为："+x);
    }

  运行结果：

非重复的元素为：9