位与进制

位运算简介展开目录

这里我假设读者有二进制的思维，知道 $(3)_{10}=(011)_2$ 将十进制转换为二进制的方法

&(与)、|(或)、^(异或)、~(非 / 取反)
>> 和 << 运算符将二进制位进行右移或者左移操作
>>> 运算符将用 0 填充高位；>> 运算符用符号位填充高位，没有 <<< 运算符
对于 int 型，1<<35 与 1<<3 是相同的，左边的操作数是 int 的时需对右侧操作数模 32，而左边的操作数是 long 型时需对右侧操作数模 64

关于上面的说明，这里还是补充一下，因为并不是所有人都了解位运算

<< 的运算规则：按二进制形式把所有的数字向左移动对应的位数，高位移出（舍弃），低位的空位补零。以 3<<2 为例，首先把 3 转换为二进制数字 0000 0000 0000 0000 0000 0000 0000 0011（int 型是 4 个字节，1 个字节 8 位，所以 int 是 32 位），然后将上面的二进制数字向左移动 2 位后面补 0 得到 0000 0000 0000 0000 0000 0000 0000 1100

在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以 2 的 1 次方，左移 n 位就相当于乘以 $2^n$

>> 的运算规则：按二进制形式把所有的数字向右移动对应位数，低为移出（舍弃），高位的空位补符号位，即正数补零，负数补 1. 以 11>>2 为例，首先把 11 转换为二进制数字 0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的两个数字移出，因为该数字是正数，所以在高位补零，则得到的最终结果是 0000 0000 0000 0000 0000 0000 0000 0010

右移一位相当于除以 2，右移 n 位相当于除以 $2^n$

>>> 运算规则：和 >> 大致相同，区别在于不论是正数还是负数，高位都补零

位运算的奇巧淫技展开目录

判断奇偶位（x & 1 == 1? 奇：偶）
获取二进制位是 1 还是 0
交换两个整数变量的值（t = a ^ b;a ^= t;b ^= t;）
不用判断语句，求整数的绝对值 (a ^ (a>> 31)) + (a >>> 31)
结合律 (a^b)^c==a^(b^c)
对于任何数 x，都有 x^x=0，x^0=x，同自己求异或为 0，同 0 求异或为自己
自反性 a^b^b=a^0=a, 连续和同一个因子做异或，最终结果为自己

题 1：找出唯一成对的数展开目录

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

题解展开目录

位运算总共就那么几条性质，假设一个数组中的值分别是 1,2,3,4,2，2 是重复的元素，那么应该怎么把它挑出来呢，最开始想到的方法肯定是两重循环枚举，时间复杂度是 O ( $n^2$ )，不太好，想想怎么用位运算解决这道题，根据 a^a=0,a^0=a 这两条性质，我们可以把数组中的元素全部异或起来，然后再异或一遍不重复的所有元素，就是 (1^2^3^4^2)^(1^2^3^4)，这样把它们凑起来，最后结果就应该是 2^2^2=2^0=2，正好是要找的重复元素

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = 1001,sum1 = 0,sum2 = 0;
        int[] arr = new int[n];
        for(int i = 0;i < n - 1;i++) {
            arr[i] = i + 1;
            sum1 ^= arr[i];
        }
        arr[n - 1] = new Random().nextInt(n);//随机数，1-n
        sum2 = sum1 ^ arr[n - 1];
        int idx = new Random().nextInt(n);//随机选取一个下标
        {//交换
            int t = arr[idx];
            arr[idx] = arr[n - 1];
            arr[n - 1] = t;
        }
        /*for(int i = 0;i < n;i++) {
            System.out.print(arr[i] + " ");
        }*/
        System.out.println(sum1 ^ sum2);
    }
}

题 2：找出落单的数展开目录

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

题解展开目录

这道题比上一道题还简单，这道题直接将所有的值全部异或起来，得到的结果就是落单的数了

题 3：二进制中 1 的个数展开目录

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

题解展开目录

第一种方法：假设这个数是 3，其二进制为 011，首先将 011&001，判断得出来的结果是否等于 001，如果等于，说明这个第 1 位是 1；然后将 011&010，判断得出来的结果是否等于 010，如果等于，说明这个第 2 位是 1，一直进行下去，判断 31 位

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int cnt = 0;
        for(int i = 0;i < 32;i++) 
            if(((1 << i) & n) == (1 << i))
                cnt++;
        System.out.println(cnt);
    }
}

第二种方法展开目录

第二种方法：只让要测验的数向右移。假设这个数是 3，其二进制为 011，首先将 011&001，判断得出来的结果是否等于 001，如果等于，说明这个第 1 位是 1；然后将 001&001，判断得出来的结果是否等于 001，如果等于，说明这个第 2 位是 1，一直进行下去，判断 31 位

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int cnt = 0;
        for(int i = 0;i < 32;i++) 
            if(((n >>> i) & 1) == 1)
                cnt++;
        System.out.println(cnt);
    }
}

第三种方法展开目录

第三种方法：还是假设这个数是 3，那我们让 3 变成 0 的过程中肯定是要消掉 1 的，消掉多少次 1，就表示 3 的二进制中有多少个 1。关键就在于，如何消掉 011 中的 1，我们首先让 011 减 1，那么 011 就变成了 010，然后让 011&010，就得到了 010，然后再让 010 减 1，那么 010 就变成了 001，然后让 010&001，就得到了 000，转换成伪代码的形式就是，a = (a - 1) & a，它的效果就是消掉最低位上的 1，依次消掉所有最低位上的 1，最后不久变成了 0 吗

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int cnt = 0;
        while(n != 0) {
            n = (n - 1) & n;
            cnt++;
        }
        System.out.println(cnt);
    }
}

题 4：是不是 2 的整数次方展开目录

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

题解展开目录

这道题比较好想，判断一个数是不是 2 的整数次方，其实就是判断这个数的二进制数是不是有且仅有一个 1，这个和上面那道题很相似，仔细想想，直接给出代码了

代码展开目录

if((n & (n - 1)) == 0)

题 5：将整数的奇偶位互换展开目录

假设这个数是 9，二进制就是 1001，那么得到的结果就是 0110

题解展开目录

首先我们需要两个个数

a = 0x55555555
b = 0xaaaaaaaa

a 和 b 都是 16 进制数，转换为二进制分别是 0101 0101 0101...，1010 1010 1010...（因为 1010 对应的十进制是 10，而 10 在 16 进制中是 a，0101 也同理），然后将需要改变的数 n 分别对 a 和 b 进行 & 运算得到 c 和 d，然后将 c 向左移 1 位，将 d 向右移 1 位，再分别进行异或，就得到所求结果，看下面示例

n = 1001
a = 0101
b = 1010
c = n & a = 0001
d = n & b = 1000
res = (c << 1) ^ (d >> 1) = 0110

题 6：0-1 间浮点实数的二进制表示展开目录

给定一个介于 0 和 1 之间的实数，（如 0.625），类型为 double，打印他的二进制表示（0.101），如果该数字无法精确地用 32 位以内地二进制表示，则打印 “ERROR”

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        double num = cin.nextDouble();
        StringBuilder sb = new StringBuilder("0.");
        while(num > 0) {
            double r = num * 2;
            if(r >= 1) {
                num = r - 1;
                sb.append("1");
            } else {
                num = r;
                sb.append("0");
            }
        }
        if(sb.length() > 34) 
            System.out.println("ERROR");
        else
            System.out.println(sb.toString());
    }
}

题 7：出现 k 次和出现 1 次的数展开目录

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

题解展开目录

这道题有很多种做法，但是这里我们只考虑如何利用进制的方法去做，多的也不说，大家只要记住一个结论 k 个相同的 k 进制数做不进位加法结果为 0。举个例子，3 个相同的三进制数，假设个这个数是 2，2 的三进制是 011，所以三个 011 做不进位加法结果就是 011+011+011=000；再比方说 10 个十进制数相加，假设这个数是 10，做不进位加法最后结果也是 0

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int[] arr = {3,3,3,5,7,7,7,8,8,8,6,6,6};
        int len = arr.length;
        char[][] kRadix = new char[len][];
        int k = 3;
        int maxlen = 0;
        //转换成k进制字符数组
        //对于每个数字
        for(int i = 0;i < len;i++) {
            kRadix[i] = new StringBuilder(Integer.toString(arr[i],k)).reverse().toString().toCharArray();
            if(maxlen < kRadix[i].length)
                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);
    }
}