如何在C语言中实现仅对二进制最后一个1及低位的位取反？

首先，你的描述和例子存在一点歧义，我分两种情况给出高效位运算实现：

情况1：符合你给出的例子（取反所有有效位，即最高位1到最低位） #

比如10（1010）→5（0101），5（101）→2（010），本质是对n的二进制中最高位1及所有更低位取反。

实现方法： #

通过构造一个掩码，掩码的二进制是与n有效位数相同的全1序列，然后将n与该掩码异或即可。

方法A：利用编译器内置函数（最快）

对于32位整数，可通过__builtin_clz（统计前导零个数）快速计算掩码：

int flip_bits(int n) {
    int leading_zeros = __builtin_clz(n);
    int mask = (1 << (32 - leading_zeros)) - 1;
    return n ^ mask;
}

• 解释：__builtin_clz(n)返回n的32位二进制中前导零的数量，由此可算出n的有效位数为32 - leading_zeros，构造全1掩码后异或n，就得到所有有效位取反的结果。

方法B：纯位运算构造掩码（无依赖）

如果不能用内置函数，可通过移位或运算构造掩码：

int flip_bits(int n) {
    int mask = n;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return n ^ mask;
}

• 解释：通过不断将掩码右移并与自身或运算，最终会把n的最高位1以下的所有位都置为1，得到全1的有效位掩码，异或后完成取反。

情况2：符合你描述的需求（仅取反最后一个1（最右边的1）及其更低位） #

比如10（1010）→9（1001），5（101）→4（100），即只取反最右边的1和它右侧的所有位。

实现方法： #

先找到最右边的1对应的数值（n & -n），然后构造掩码为该数值的2倍减1，最后异或n：

int flip_last_one_and_lower(int n) {
    int last_one = n & -n; // 得到最右边的1对应的数值，比如10的话是2（10）
    int mask = (last_one << 1) - 1; // 构造掩码，比如2<<1-1=3（11）
    return n ^ mask;
}

• 解释：n & -n利用补码特性，直接提取出n最右边的1；将其左移1位再减1，得到从最低位到该1位置的全1掩码，异或后就只取反这些位。

两种方法都是O(1)时间复杂度，完全不用担心n<=1e6的效率问题。

内容的提问来源于stack exchange，提问作者penguinn