位运算

题目要求 给你一个非空整数数组 nums。 数组中只有一个元素出现一次，其余每个元素都恰好出现两次。题目要求返回那个只出现一次的元素。 LeetCode 提供的方法接口是： singleNumber(nums: List[int]) -> int 除了返回正确答案，解法还需要满足两个要求： 时间复杂度是 O(n)。 只使用 O(1) 额外空间。 示例 1 输入：nums = [2,2,1] 输出：1 2 出现两次，只有 1 出现一次。 示例 2 输入：nums = [4,1,2,1,2] 输出：4 1 和 2 都能找到相同的另一个元素，最后只有 4 没有配对。 示例 3 输入：nums = [1] 输出：1 数组只有一个元素时，它就是答案。 约束 1 <= nums.length <= 3 * 10^4 -3 * 10^4 <= nums[i] <= 3 * 10^4 除一个元素只出现一次外，其余元素都恰好出现两次。 Step 1：先把“只出现一次”说准确 先看： nums = [4,1,2,1,2] 在这个很小的数组里，我们可以用眼睛寻找相同的数字： ...

题目要求 给定一个正整数 n，返回它的二进制表示中 1 的个数。这个数量也叫 Hamming weight。 LeetCode 提供的方法接口是： hammingWeight(n: int) -> int 示例 1 输入：n = 11 二进制：1011 输出：3 示例 2 输入：n = 128 二进制：10000000 输出：1 约束 1 <= n <= 2^31 - 1 输入处于题目给定的非负整数范围内。 虽然当前约束从 1 开始，后面的实现也会自然处理 n = 0，并返回 0。 Step 1：先明确到底在数什么 先看一个不使用十进制表示的小任务： n = 101100₂ 从左到右可以看到三个 1： 1 0 1 1 0 0 ^ ^ ^ 所以答案是 3。 当前 baseline 是： 先看出整数的二进制表示，再人工统计其中的 1。 这个 baseline 的 break 是： ...

题目要求 给定一个非负整数 n，返回一个长度为 n + 1 的数组 answer。 其中： answer[i] = 整数 i 的二进制表示中 1 的数量 需要回答的范围包含 0 和 n。 LeetCode 提供的方法接口是： countBits(n: int) -> List[int] 示例 1 输入：n = 2 输出：[0,1,1] 对应关系是： 0 -> 0 -> 0 个 1 1 -> 1 -> 1 个 1 2 -> 10 -> 1 个 1 示例 2 输入：n = 5 输出：[0,1,1,2,1,2] 约束 0 <= n <= 10^5 Step 1：这次要回答 0 到 n 的所有数字 LeetCode 191 只要求统计一个整数。现在看 n = 5： ...

副标题 / 摘要 2 的幂判断是位运算最经典的模板题之一。本文按 ACERS 结构讲清原理、工程场景与常见误区，并给出可复用的多语言实现。 预计阅读时长：8~12 分钟 标签：位运算、二进制、数学 SEO 关键词：Power of Two, 2 的幂, 位运算, bit manipulation, LeetCode 231 元描述：用位运算 O(1) 判断 2 的幂，含工程应用、复杂度分析与多语言代码。 目标读者 刚开始接触位运算的算法学习者 想沉淀“位运算模板题”的中级开发者 在系统/后端中需要对齐、分片、容量判断的工程师 背景 / 动机 “2 的幂”是很多工程系统的隐含约束：哈希表容量、内存对齐、任务分片、FFT 窗口大小等。 如果每次判断都用循环或除法，不仅慢，而且容易写出边界错误。 位运算提供了 O(1) 的稳定判断，是可长期复用的基础能力。 核心概念 二进制表示：2 的幂在二进制中只有一个 1，其余全是 0 位与运算：n & (n - 1) 会清除最低位的 1 必要条件：n > 0，排除 0 和负数 A — Algorithm（题目与算法） 题目还原 给定一个整数 n，判断它是否为 2 的幂。 如果是返回 true，否则返回 false。 输入输出 名称 类型 说明 n int 待判断整数 返回 bool 是否为 2 的幂 示例 1 输入: n = 1 输出: true 解释: 2^0 = 1 示例 2 输入: n = 12 输出: false 解释: 12 的二进制是 1100，含多个 1 C — Concepts（核心思想） 核心原理：一次位运算完成判断 2 的幂的二进制形态：1000...000（只有一个 1） n - 1 会把这个 1 变成 0，右侧全部变成 1 因此： n = 1000...000 n - 1 = 0111...111 n & (n - 1) = 0000...000 结论： ...