跳到主要内容

位操作

位操作是面试中的高频考点，主要考察对二进制数的理解、位运算符的使用以及位运算技巧。

面试题 05.01. 插入​

题目描述​

给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j。编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。

示例 1：

输入：N = 1024(10000000000), M = 19(10011), i = 2, j = 6
输出：N = 1100(10001001100)

示例 2：

输入：N = 0, M = 31(11111), i = 0, j = 4
输出：N = 31(11111)

解题思路​

  1. 将 N 的第 i 到 j 位清零
  2. 将 M 左移 i 位
  3. 将处理后的 N 与 M 进行或运算

Java 代码实现​

class Solution {
    public int insertBits(int N, int M, int i, int j) {
        int mask = ((1 << (j - i + 1)) - 1) << i;
        mask = ~mask;
        N = N & mask;
        M = M << i;
        return N | M;
    }
}

面试题 05.02. 二进制数转字符串​

题目描述​

二进制数转字符串。给定一个介于 0 和 1 之间的实数（如 0.72），类型为 double，打印它的二进制表达式。如果该数字无法精确地用 32 位以内的二进制表示，则打印 "ERROR"。

示例 1：

输入：0.625
输出："0.101"

示例 2：

输入：0.1
输出："ERROR"

解题思路​

每次将小数部分乘以 2，如果结果大于等于 1，则当前位为 1，否则为 0。重复此过程直到小数部分为 0 或超过 32 位。

Java 代码实现​

class Solution {
    public String printBin(double num) {
        StringBuilder sb = new StringBuilder("0.");
        while (num != 0) {
            num *= 2;
            if (num >= 1) {
                sb.append('1');
                num -= 1;
            } else {
                sb.append('0');
            }
            if (sb.length() > 32) {
                return "ERROR";
            }
        }
        return sb.toString();
    }
}

面试题 05.03. 翻转数位​

题目描述​

给定一个 32 位整数 num，你可以将一个数位从 0 变为 1。请编写一个程序，找出你能够获得的最长的一串 1 的长度。

示例 1：

输入: num = 1775(11011101111)
输出: 8

示例 2：

输入: num = 7(0111)
输出: 4

解题思路​

使用滑动窗口思想。维护一个窗口，窗口内最多包含一个 0。当窗口内有两个 0 时，移动左边界直到只剩一个 0。

Java 代码实现​

class Solution {
    public int reverseBits(int num) {
        int maxLen = 0;
        int left = 0;
        int zeroCount = 0;
        for (int right = 0; right < 32; right++) {
            if ((num & (1 << right)) == 0) {
                zeroCount++;
            }
            while (zeroCount > 1) {
                if ((num & (1 << left)) == 0) {
                    zeroCount--;
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

面试题 05.04. 下一个数​

题目描述​

下一个数。给定一个正整数，找出与其二进制表达式中 1 的个数相同且大小最接近的那两个数（一个略大，一个略小）。

示例 1：

输入：num = 2（或者 0b10）
输出：[4, 1] （或者 [0b100, 0b1]）

示例 2：

输入：num = 1
输出：[2147483647, -1]

解题思路​

找较大的数： 找到最右边的 01 模式，将其变为 10，然后将右边的 1 都移到最右边。

找较小的数： 找到最右边的 10 模式，将其变为 01，然后将右边的 1 都移到紧邻这个位置。

Java 代码实现​

class Solution {
    public int[] findClosedNumbers(int num) {
        int[] result = new int[]{-1, -1};
        
        int next = getNext(num);
        if (next != -1) {
            result[0] = next;
        }
        
        int prev = getPrev(num);
        if (prev != -1) {
            result[1] = prev;
        }
        
        return result;
    }
    
    private int getNext(int num) {
        int c = num;
        int c0 = 0, c1 = 0;
        while ((c & 1) == 0 && c != 0) {
            c0++;
            c >>= 1;
        }
        while ((c & 1) == 1) {
            c1++;
            c >>= 1;
        }
        if (c0 + c1 == 31 || c0 + c1 == 0) {
            return -1;
        }
        int p = c0 + c1;
        num |= (1 << p);
        num &= ~((1 << p) - 1);
        num |= (1 << (c1 - 1)) - 1;
        return num;
    }
    
    private int getPrev(int num) {
        int c = num;
        int c0 = 0, c1 = 0;
        while ((c & 1) == 1) {
            c1++;
            c >>= 1;
        }
        if (c == 0) {
            return -1;
        }
        while ((c & 1) == 0 && c != 0) {
            c0++;
            c >>= 1;
        }
        int p = c0 + c1;
        num &= ((~0) << (p + 1));
        int mask = (1 << (c1 + 1)) - 1;
        num |= mask << (c0 - 1);
        return num;
    }
}

面试题 05.06. 整数转换​

题目描述​

整数转换。编写一个函数，确定需要改变几个位才能将整数 A 转成整数 B。

示例 1：

输入：A = 29 （或者 11101）, B = 15（或者 01111）
输出：2

示例 2：

输入：A = 1，B = 2
输出：2

解题思路​

计算 A XOR B 的结果中 1 的个数，即为需要改变的位数。

Java 代码实现​

class Solution {
    public int convertInteger(int A, int B) {
        int xor = A ^ B;
        int count = 0;
        while (xor != 0) {
            count++;
            xor = xor & (xor - 1);
        }
        return count;
    }
}

面试题 05.07. 配对交换​

题目描述​

配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位 0 与位 1 交换，位 2 与位 3 交换，以此类推）。

示例 1：

输入：num = 2（或者 0b10）
输出：1（或者 0b01）

示例 2：

输入：num = 3
输出：3

解题思路​

  1. 提取所有偶数位，左移一位
  2. 提取所有奇数位，右移一位
  3. 将两部分合并

Java 代码实现​

class Solution {
    public int exchangeBits(int num) {
        int even = num & 0xAAAAAAAA;
        int odd = num & 0x55555555;
        return (even >> 1) | (odd << 1);
    }
}

面试题 05.08. 绘制直线​

题目描述​

绘制直线。有个单色屏幕存储在一个一维数组中，其中 32 个像素构成一个无符号整数。屏幕宽度为 w，请绘制一条从点 (x1, y) 到点 (x2, y) 的水平线。

给定一个一维数组 screen，屏幕宽度 w，以及直线的开始位置 x1、结束位置 x2 和纵坐标 y，返回绘制后的屏幕数组。

示例 1：

输入：screen = [0,0,0,0,0], w = 5, x1 = 1, x2 = 3, y = 0
输出：[0,14,0,0,0]

解题思路​

计算起始和结束的字节位置，以及对应的位掩码。对于完整的字节，设置为 0xFF；对于部分字节，使用掩码设置相应的位。

Java 代码实现​

class Solution {
    public int[] drawLine(int[] screen, int width, int x1, int x2, int y) {
        int startOffset = x1 / 8;
        int endOffset = x2 / 8;
        int firstFullByte = startOffset;
        int lastFullByte = endOffset;
        
        int rowStart = y * (width / 8);
        
        if (startOffset == endOffset) {
            int mask = ((0xFF >> (x1 % 8)) & (0xFF << (7 - x2 % 8)));
            screen[rowStart + startOffset] |= mask;
        } else {
            int startMask = 0xFF >> (x1 % 8);
            int endMask = 0xFF << (7 - x2 % 8);
            screen[rowStart + startOffset] |= startMask;
            screen[rowStart + endOffset] |= endMask;
            for (int i = startOffset + 1; i < endOffset; i++) {
                screen[rowStart + i] = (byte) 0xFF;
            }
        }
        return screen;
    }
}