【位运算专题】剑指 Offer 15. 二进制中1的个数

共以下 9 个回答

• 小肸 永久会员 2023年9月6日 上午10:05

  public class Solution {
      // you need to treat n as an unsigned value
      public int hammingWeight(int n) {
          //0（二进制表示为0000）和一个数与运算，相当于这个数的二进制按位取0
          //1(二级制表示为0001)和一个数与运算，相当于这个数的二进制最后一位保留，高位都置为0
          int res = 0;
          //依次判断n的二进制每一位是否为1，时间复杂度为O(32)，对于32位整数而言
          // for (int i = 0; i < 32; i ++) {
          //     if (n & (1 << i) != 0) {
          //         res ++;
          //     }
          // }
          //使用n & (n - 1)会将n的最后一位1置为0这一个特性判断
          //时间复杂度为O(logN)，logN为N的二进制表示中1个总个数
          while (n != 0) {
              n &= (n - 1);
              res ++;
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sc_Yang 普通 2023年9月6日 上午7:47

  位运算熟能生巧，且需注意if中与或非计算的优先级低于等于的优先级

  class Solution {
  public:
      int hammingWeight(uint32_t n) {
          int count=0;
          while(n!=0){
              if((n&1)==1){
                  count++;
              }
              n = n>>1;
          }
          return count;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Sheng 永久会员 2023年9月4日 下午8:08

  自己写的好像没用提示给出的公式。看看答案

          int tmp = n;
          int num = 0;
          for(int i=0; i<32; i++)
          {
              if((tmp & 1) == 1) {
                  num++;
              }
              tmp = tmp >> 1;
          }
          return num;
  

  0 赞同 0 条回复

  登录以回复
• sincere 普通 2023年9月2日 下午9:27

  • 思路：要统计n的二进制数有多少个1，n&1=1表示最后一位是1，=0表示最后一位是0；可以循环n，每次与1然后n右移一位，直到n=0
  • 复杂度：时间复杂度O(logn)，空间复杂度O(1)

  public class Solution {
  
      public int hammingWeight(int n) {
          int sum = 0;
          while (n != 0) {
              sum += n & 1;
              n >>>= 1;
          }
          return sum;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• c 普通 2023年8月31日 下午7:07

  按位检查

  public class Solution {
      // you need to treat n as an unsigned value
      public int hammingWeight(int n) {
          int res = 0;
          for(int i = 0;i<32;i++){
              if((n&(1<<i))!=0){
                  res++;
              }
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年8月29日 下午11:13

  1、利用Integer.toBinaryString()

  public class Solution {
      // you need to treat n as an unsigned value
      public int hammingWeight(int n) {
          return Integer.toBinaryString(n).replace("0", "").length();
      }
  }
  

  2、通过n&(n-1),移除最右边的1

  public class Solution {
      public int hammingWeight(int n) {
          int count = 0;
          while(n != 0){
              n = n & (n-1);
              count++;
          }
          return count;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年8月29日 下午7:30

  利用n&(n-1)消除最右边的1

  public class Solution {
      // you need to treat n as an unsigned value
      public int hammingWeight(int n) {
          int count = 0;
          while (n != 0) {
              // n & (n-1) 可以消除n最右边的一个1(二进制表示)
              n = n & (n - 1);
              count++;
          }
          return count;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 行动派小彩笔 普通 2023年8月29日 下午7:01

  // 二进制位移，计算有多少个1
  class Solution {
  public:
      int hammingWeight(uint32_t n) {
          int ans=0;
          while(n)
          {
              if(n&1==1) ++ans;
              n = n>>1;
          }
          return ans;
      }
  };
  // 方法二
  // 通过n&(n-1),移除最右边的1
  class Solution {
  public:
      int hammingWeight(uint32_t n) {
          int ans=0;
          while(n)
          {
              n&=n-1;
              ans+=1;
          }
          return ans;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• JustRtn 普通 2023年8月29日 下午2:48

  时间复杂度：O(logN)， 空间复杂度：O(1)

  class Solution {
  public:
      int hammingWeight(uint32_t n) {
          int size = 0;
          while (n) {
              n &= n-1;
              size++;
          }
          return size;
      }
  };
  

  0 赞同 0 条回复

  登录以回复