Java 位运算算法题目练习 | 极客日志

Javajava算法

Java 位运算算法题目练习

Java 语言中关于位运算的经典算法题目，涵盖汉明距离、比特位计数、只出现一次的数字（一、二、三）、判断字符是否唯一、丢失的数字、两数之和及消失的两个数字等 LeetCode 题目。文章详细解析了每道题的思路，包括异或运算性质、位图思想、动态规划优化及时间复杂度分析，并提供了完整的 Java 代码实现，旨在帮助开发者深入理解位运算技巧及其在实际编程中的应用。

狂少发布于 2026/3/30更新于 2026/4/130 浏览

Java 位运算算法题目练习

汉明距离

题目解析：判断两个数的对应的二进制位不同的个数。直接判断 (x>>i)&1 和 (y>>i)&1，先获取对应二进制位，再判断是否相等即可。

class Solution {
    public int hammingDistance(int x, int y) {
        int count = 0;
        // 从后向前依次取出二进制位，进行比较
        for (int i = 0; i < 31; i++) {
            if (((x >> i) & 1) != ((y >> i) & 1)) {
                count++;
            }
        }
        return count;
    }
}

比特位计数

题目解析：给了一个数 n，从 [0, n] 中，找出每一个数对应的二进制位中 1 的个数，并将其放一个长度为 (n+1) 数组中。 暴力解法：因为 n & (n-1) 每次都可以干掉最右边的 1，这样每次遇到一个数，都进行这样的操作，直到这个数变成 0，才进行下一个数的计算，时间复杂度：O(n * log n)。规律：一个正整数 x，右移一位，将会去掉最低位，变成 x / 2。但是我们可以知道，如果 x 是偶数其 1 的个数和 x / 2 是一样的，因为后面都是 0；奇数的话就要 +1。偶数：bits[x] = bits[x>>1] ：bits[x] = bits[x>>1] + 1 通过这种方法可以利用前面已经计算过的数据，不用像上面重复计算，时间复杂度：O(n)。

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

// 暴力解法
class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int x = i;
            while (x > 0) {
                // 每次干掉最右边的 1
                x = x & (x - 1);
                count++;
            }
            bits[i] = count;
        }
        return bits;
    }
}

// 根据规律优化
class Solution {
    public int[] countBits(int n) {
        // 根据规律特性，偶数 bits[x]= bits[x/2] ，奇数 +1
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }
}

class Solution {
    public int[] singleNumber(int[] nums) {
        // 先全部进行一次异或，这样得到的是其两个不同数的异或结果
        // 因为 a^b^b = a
        // 所以只需要在异或一遍
        int x = 0;
        for (int num : nums) {
            x ^= num;
        }
        int t1 = 0;
        int t2 = 0;
        // 防溢出 0 x = x == Integer.MIN_VALUE ? x : x&(-x)
        // 直接根据最右侧 1 写
        x = x & (-x);
        for (int num : nums) {
            // 等于 0 说明，找到了一个数
            if ((num & x) != 0) {
                t1 ^= num;
            } else {
                t2 ^= num;
            }
        }
        return new int[]{t1, t2};
    }
}

class Solution {
    public boolean isUnique(String astr) {
        if (astr.length() > 26) {
            return false;
        }
        // 位图的思想，只是用一个 int 来表示全部
        int bitMap = 0;
        for (int i = 0; i < astr.length(); i++) {
            int x = astr.charAt(i) - 'a';
            // 判断其对应位置的二进制位是否为 1
            if (((bitMap >> x) & 1) == 1) {
                return false;
            }
            // 如果是 0 就将这个二进制位修改成 1
            bitMap |= (1 << x);
        }
        return true;
    }
}

class Solution {
    public int missingNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i] ^ i;
        }
        // 最后还有一个其长度没有异或
        return ret ^ nums.length;
    }
}

class Solution {
    public int getSum(int a, int b) {
        // 当没有进位 a ^ b 就是结果
        while (b != 0) {
            int x = a ^ b; // 无进位相加
            int carry = (a & b) << 1; // 计算进位
            a = x;
            b = carry;
        }
        return a;
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            // 统计其数组第 i 位 2 进制之和
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            if (sum == 1) {
                // 将其第 i 位修改成 1
                ret |= (1 << i);
            }
        }
        return ret;
    }
}

class Solution {
    public int[] missingTwo(int[] nums) {
        // 先找出消失的两个数字^结果
        int ret = 0;
        for (int num : nums) {
            ret ^= num;
        }
        for (int i = 1; i <= nums.length + 2; i++) {
            ret ^= i;
        }
        // 此时的 ret 就是消失的两个数字的异或结果
        // 找出最右边的 1
        ret = ret == 0 ? ret : ret & (-ret);
        // 只根据其第 i 位进行判断即可，因为异或结果是相同为 0，不同为 1
        // 此时将其分为两类
        int t1 = 0;
        int t2 = 0;
        for (int num : nums) {
            if ((ret & num) != 0) {
                t1 ^= num;
            } else {
                t2 ^= num;
            }
        }
        for (int i = 1; i <= nums.length + 2; i++) {
            if ((ret & i) != 0) {
                t1 ^= i;
            } else {
                t2 ^= i;
            }
        }
        return new int[]{t1, t2};
    }
}

class Solution {
    public int[] missingTwo(int[] nums) {
        // 先找出消失的两个数字^结果
        int ret = 0;
        for (int num : nums) {
            ret ^= num;
        }
        for (int i = 1; i <= nums.length + 2; i++) {
            ret ^= i;
        }
        // 此时的 ret 就是消失的两个数字的异或结果
        int d = 0;
        // 为 1 的二进制位
        while (true) {
            if (((ret >> d) & 1) == 1) {
                break;
            }
            d++;
        }
        // 只根据其第 i 位进行判断即可，因为异或结果是相同为 0，不同为 1
        // 此时将其分为两类
        int t1 = 0;
        int t2 = 0;
        for (int num : nums) {
            if (((num >> d) & 1) == 0) {
                t1 ^= num;
            } else {
                t2 ^= num;
            }
        }
        for (int i = 1; i <= nums.length + 2; i++) {
            if (((i >> d) & 1) == 0) {
                t1 ^= i;
            } else {
                t2 ^= i;
            }
        }
        return new int[]{t1, t2};
    }
}