[leetcode476]数字的补数

发布于 2021-10-18  629 次阅读


https://leetcode-cn.com/problems/number-complement/

简单题 引发了一些思考

做法1:从最高位开始找最高位的1 之后找到之后的所有0 进行运算即可

#include<bits/stdc++.h>

class Solution {
public:
    int findComplement(int num) {
        int f=-1;
        for(int i=31;i>=0;i--){
          if((num>>i&1)==1){
            f=i;
            break;
          }
        }
        int ans=0;
        for (int i = 0; i < f; i++)
        {
          if(((num>>i)&1)==0) { ans|=(1<<i);}
        }
        return ans;
    }
};

做法2:利用lowbit找到最高位的1 比如0010 0000 这个数减1 0001 1111 直接与取反后的num&即可

#include<bits/stdc++.h>

class Solution {
public:
    int findComplement(int num) {
      int ans=0;
      for (int i = num; i !=0; i-=(i&-i))
      {
        ans=i;
      }
      return ~num&(ans-1);
    }
};

关于引发的思考:补码这一原因 为何~5=-6 看计算机内部的时候一定要以补码的形式去理解 5=0101(前面一堆0) 取反 1010(前面一堆1) 这个时候这个数成了负数
负数的补码是取反后加1
所以 1010这个数对应的10进制数是-1后取反 1001取反 0110(前面一堆0) 即 -6


愿风指引你的道路,愿你的刀刃永远锋利。