Leetcode Problem 1009 Complement of base 10 integer

Question

整数的补码是将二进制表示形式中的所有 0 翻转为 1，将所有 1 翻转为 0 时得到的整数。 例如，整数5在二进制中是“101”，它的补码是“010”，即整数2。 给定一个整数 n，返回它的补码。

我的解决方案-

class Solution {
public:
    int bitwiseComplement(int n) {
        int k=1;
        if(n==0){
            return k;
        }
        long int binary=0,i=0;
        while(n){
            long int bit=n&1;
            if(bit==0){
                bit=1;
            }
            else{
                bit=0;
            }
            binary=(bit*pow(10,i))+binary;
            n=n>>1;
            i++;
        }
        long int ans=0,j=0;
        while(binary!=0){
            long int digit=binary%10;
            ans=digit*pow(2,j)+ans;
            j++;
            binary=binary/10;
        }
        
        
        return ans;
        
    }
};

这里我的错误是什么？ 我所有的测试用例都运行成功，但当输入为 299475 时，输出为 224816，预期输出为 224812。 请帮助我。

Answer 1

正如评论中的其他人所建议的那样，有位翻转运算符

~

反转整数中的所有位

像“5”这样的数字是二进制的。假设一个 32 位整数。

0000000 0000000 0000000 0000101

所以应用这个：

int n = 5;
n = ~5;

为

n

制作这个：

11111111 11111111 11111111 11111010

oops，就像-6，而不是问题想要的 2。您需要重新旋转那些前导

1

位并在遇到第一个 0（从左到右）时停止。

总而言之。

int bitwiseComplement(int n) {

    if (n == 0)
    {
        return 1; // special case
    }

    int i = ~n;
    size_t bits = sizeof(n) * 8;

    // it's always a good idea to do bit-twiddling exercises
    // in the unsigned space - especially for the right shift
    unsigned int mask = 1 << (bits-1);  // this should be 0x80000000
    while (mask & i)                    // while the bit in u matching the bit in mask are both set
    {
        i = mask ^ i;                   // toggle the bit in u to zero
        mask = mask >> 1;               // mask gets shifted (e.g. 0x80000000 to 0x40000000)
    }
    return i;
}

Answer 2

selbie的回答很好。此外，该答案表明使用 ~ 运算符需要做进一步的工作。这是另一个有效的解决方案。它稍微简单一些，二进制操作的数量较少。

class Solution {
public:
    int bitwiseComplement(int n) {
        
        if(n==0){
            return 1;
        }
        int comp_op=0;
        int i=0;
        while(n){
            int bit=n&1;
            int add_val = 0;
            if (bit == 0)
                add_val = 1<<i;
            comp_op += add_val;
            n >>= 1;
            i++;
        }
        return comp_op;
    }
};

selbie 关于使用无符号整数进行位操作的观点非常正确。在这种情况下，Leet Code 问题让我们假设数字是非负数 (0 <= n < 10^9).

如果在一个有点棘手的问题中，n 可以是负数，基于

n>>1

进行和退出的while 循环不是一个好主意。我们应该根据数字表示中的位数来推进 while 循环，就像在 selbie 的答案中所做的那样。然而，如果这个 Leet Code 问题必须重新设计以允许输入负数，那么问题的陈述必须仔细和清晰地细化，关于输出的期望。

Answer 3

c++20 增加了许多有用的位相关函数。如果您能找到一个可以生成方便的基数 111...111（具有适当数量的 1）的一个，那么您可以异或 (^=) 您的原始数字。这样的数字很容易通过从 std::bit_ceil 的结果中减去 1 来产生。

转成unsigned更靠谱。您还需要一个最新的编译器。

可悲的是，n=0 是一个特例......如果你想包括它然后单独对待它。

#include <iostream>
#include <bit>
 
int bitwiseComplement( int n )
{ 
   return n ^= std::bit_ceil( (unsigned)(n+1) ) - 1;
}

int main()
{
   std::cout << bitwiseComplement( 299475 );
}

输出：

224812