- 正确答案：将一个整数的二进制表示中所有为1的位全部移动到最低位（即右侧连续排列），可以通过统计二进制中1的个数，然后构造一个新的数，其低k位全为1（k是原数中1的个数），其余位为0来实现。例如：输入：10（二进制为 1010）输出：3（二进制为 0011）输入：12（二进制为 1100）输出：3（二进制为 0011）输入：7（二进制为 0111）输出：7（保持不变） - 解答思路： 1. 首先统计原整数n的二进制表示中1的个数，记为count。 2. 然后构造一个新的整数，使其低count位全为1，其余位为0。 - 这可以通过 (1 << count) - 1 来实现。 3. 返回该新整数。这个方法的关键在于理解：无论原来1在什么位置，最终目标是让这些1全部集中在最低位，形成一个形如 00...011...1 的数。 - 深度知识讲解：这个问题考察的是对位运算的深刻理解，包括： 1. 位操作基础： - >> 右移：用于遍历每一位 - & 1：判断最低位是否为1 - << 左移：用于构造新数 - - 1 操作与全1序列的关系：(1 << k) - 1 得到低k位全为1的数 2. 统计二进制中1的个数的方法： - 方法一：循环右移并&1判断 - 方法二：使用 n & (n-1) 消除最右边的1（Brian Kernighan算法） - 方法三：查表法或使用内置函数如 __builtin_popcount（GCC） 3. 数据表示与底层原理： - 整数在计算机中以补码形式存储 - 位运算是CPU最基础的操作，效率极高 - 移位和加减法可以替代乘除法优化性能 4. 时间复杂度分析： - 使用 n & (n-1) 方法：O(k)，k为1的个数 - 使用右移遍历：O(log n)，即位数 - 构造结果：O(1) 5. 边界情况处理： - n = 0：返回0 - n < 0：取决于是否考虑负数。若只处理无符号整数或正整数，则可忽略；若需处理负数，应明确使用无符号类型。 - 代码示例（C++）： ``` #include using namespace std; int moveOnesToLowestBits(int n) { if (n == 0) return 0; // 使用 n & (n-1) 方法统计1的个数 int count = 0; unsigned int num = n; // 转为无符号防止负数右移问题 while (num) { num &= (num - 1); count++; } // 构造低count位为1的数 return (1 << count) - 1; } // 另一种实现：逐位统计 int moveOnesToLowestBits_v2(int n) { int count = 0; unsigned int num = n; while (num) { count += (num & 1); num >>= 1; } return (1 << count) - 1; } // 测试函数 int main() { cout << moveOnesToLowestBits(10) << endl; // 输出 3 cout << moveOnesToLowestBits(12) << endl; // 输出 3 cout << moveOnesToLowestBits(7) << endl; // 输出 7 cout << moveOnesToLowestBits(0) << endl; // 输出 0 return 0; } ``` - 扩展知识点： 1. 相关位运算技巧： - 获取最低位的1：x & (-x) - 清除最低位的1：x & (x-1) - 判断是否为2的幂：x & (x-1) == 0 且 x != 0 2. 实际应用场景： - 位压缩（bit packing） - 哈希函数设计 - 编解码算法（如Gray码、Huffman编码中的位操作） - GPU编程中优化内存访问模式 3. 高级变种问题： - 将所有0移到最低位 - 保持1的相对顺序移动到高位 - 分离奇偶位等 4. 性能优化： - 使用内置函数 __builtin_popcount 快速统计1的个数 - 查表法预计算8位字节的popcount 总结：该问题本质是“位重排”操作，核心思想是“先统计后重建”。它不仅测试候选人对位运算的掌握程度，也考察其能否将复杂操作分解为简单步骤的能力。在实际系统编程、算法优化中，这类技巧非常实用。

字节一面

全站热榜

创作者周榜