【位运算专题】剑指 Offer 15. 二进制中1的个数-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年4月19日下午10:06

public class Solution {
    // 利用公式 n & n-1，每计算一次减去一次1
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n = n & (n-1);
            count ++;
        }
        return count;
    }
}

0 赞同 0 条回复

宁永久会员 2023年1月14日下午4:18

记住n = n & (n – 1);可以消除最右侧的1

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

0 赞同 0 条回复

PatNick 普通 2023年1月10日上午11:12

def hammingWeight(n):
    num = 0
    while n != 0:
        # 消除n的最后一位1
        n = n & (n-1)
        num += 1
    return num

0 赞同 0 条回复

lucca 普通 2023年1月9日上午9:44

lowbit 取最低位1

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        while (n != 0) {
            n -= (n & -n);
            cnt++;
        }
        return cnt;
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月2日下午3:36

func hammingWeight(num uint32) int {
    //将2^i和num进行与运算，当且仅当n的第i为不为0时，运算结果才不会0
    res := 0
    for i :=0;i < 32;i++{
        if (1 << i & num) > 0{ //2^i 计算方式为1 << i,与运算为&
            res++
        }
    }
    return res
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:45

class Solution {
public:
    int hammingWeight(uint32_t n) {
        if(n==0) return 0;
        int count = 0;
        while(n){
            count+=n%2; //除2取余法
            n = n/2;
        }
        return count;
    }
};

0 赞同 0 条回复

xye 普通 2022年11月23日下午4:38

func hammingWeight(n uint32) int {
    count := 0
    for n != 0 {
        count = count + 1
        n = n & (n - 1)//将最右边的1变成0
    }
    return count
}

时间O(log2N) 空间O(1)

0 赞同 0 条回复

刺猬普通 2022年11月22日下午3:19

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

时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年11月20日下午3:20

时间复杂度：O（logN）
空间复杂度：O（1）

class Solution:
    def hammingWeight(self, n: int) -> int:
        sum = 0
        while n != 0:
            # n 的二进制位中的最低位的 11 变为 00 
            n = n & (n - 1)
            sum += 1
        return sum

0 赞同 0 条回复

Tolkien 永久会员 2022年11月15日下午9:19

/**
     * 时间复杂度：O(logn)
     * 空间复杂度：O(1)
     */
    public static int hammingWeight(int n) {
        int count = 0;

        while (n != 0) {
            // 执行以下操作会使n最右边的1变为0
            n = n & (n-1);
            // 情况1：最后一位为1，如1111
            // 1111 & 1110 = 1110
            // 情况2：最后一位为0，如1110
            // 1110 & 1101 = 1100
            // 两种情况都使最右边
            count ++;
        }

        return count;
    }

0 赞同 0 条回复

鸿渐普通 2022年11月15日下午8:11

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
         //位运算公式的应用 n& (n-1) 得到的结果是去掉最右侧的1
        //比如n=1001 相与之后就是1000 ，1010 相与之后就是1000

        //所以我们只要在所有的1被与完之前统计与操作的次数就行
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

0 赞同 0 条回复

小肸永久会员 2022年11月15日下午4:10

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            // 把n最右边的1变成0
            n &= (n - 1);
            res ++;
        }
        return res;
    }
}

0 赞同 0 条回复

Y7n05h 普通 2022年11月14日下午5:18

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

时间复杂度：O(1)

0 赞同 0 条回复

@ 普通 2022年11月14日上午9:10

public class Solution {

    //方法一：使用 >>> 1 逐位判断
    //时间复杂度 O(logN) 
    //空间复杂度 O(1)：变量res使用常数大小额外空间。
    public int hammingWeight1(int n) {
        int i = 0;
        while (n != 0) {
            if ((n & 1) == 1)
                i++;

            n >>>= 1;

        }

        return i;

    }


    //方法二:巧用 n & n - 1
    //时间复杂度 O(M) ：M为二进制数字n中1的个数，则需循环M次（每轮消去一个1 ），占用 O(M)O(M)O(M) 。
    //空间复杂度 O(1)：变量res使用常数大小额外空间。


    public int hammingWeight2(int n) {
        int i = 0;
        while (n != 0) {
            n &= n - 1;
            i++;
        }

        return i;

    }

}

0 赞同 0 条回复

Whatever 永久会员 2022年11月13日下午9:39

时间O(n)，空间O(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 & (n-1);
            count++;
        }
        return count;
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月11日下午10:24

 // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //时间复杂度为O(n)
        //空间复杂度为O(1)
        int count=0;
        while (n!=0){
            //n&(n-1)结果是把n的二进制中的最低位的1变为0；
            //每次执行你&（n-1)表示不断的把n最低位的1转为0 ，计算一下次数就是1的个数
            n=n&(n-1);
            count++;
        }
        return count;
    }

0 赞同 0 条回复

庄重普通 2022年11月11日上午9:53

// 思路：使用&运算(全1为1，其余为0)
//     1.公式 n & (n-1) 会使二进制最右边的一个1变成0
//     2.n = 1000 1000; n-1 = 1000 0111
//     3。进行&运算，n & (n-1) = 1000 0000
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        while(n != 0){
            n &= n-1;
            ++sum;
        }
        return sum;
    }
};
//时间复杂度O(logn)
//空间复杂度O(1)

0 赞同 0 条回复

y 普通 2022年11月10日下午11:31

var hammingWeight = function(n) {
    let count = 0;
   while(n) {
       n = n & (n-1);
       count ++;
   }
   return count;
};

时间：O(n)
空间：O(1)

0 赞同 0 条回复

天然普通 2022年11月10日下午10:17

现学现卖，哈哈哈哈，用位运算去统计空间O(n)

class Solution:
    def hammingWeight(self, n: int) -> int:
        num = 0
        while n:
            if n&1==1: num+=1
            n = n>>1
        return num

空间O(logn)
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res ++;
            n = n & (n-1);
        }
        return res;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年11月10日下午4:10

空间O(logn)
时间O(1）

public class Solution {
    // you need to treat n as an unsigned value
    //两种方法：1.除以2.奇数
    public int hammingWeight(int n) {
        int count = 0;
        while(n!=0){
            if(n%2==1){
                count++;
            }
            n = n/2;

        }
        return count;
    }
    //位运算法
    public int hammingWeight(int n){
        int count = 0;
        while(n!=0){
            n = n&(n-1);
            count++;
        }
        return count;
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年11月10日上午9:17

技巧n&(n-1)

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

0 赞同 0 条回复

cxc 普通 2022年11月10日上午12:25

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
        while(n != 0) {
            sum++;
            //不断让当前的 n 与 n−1 做与运算，直到 n 变为 0 即可
            n = n&(n-1);
        }
        return sum;
    }
}

0 赞同 0 条回复

派大星普通 2022年11月9日下午10:49

public class Solution {
//一个二进制数与这个数减一做与运算，可以消掉右边数的第一个一
//时间复杂度O(logn)
//空间复杂度O(1)
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
        while(n != 0){
            n = n & (n - 1);
            sum ++;
        }
        return sum;
    }
}

0 赞同 0 条回复

lobort 普通 2022年11月9日下午9:39

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0){
            // 只有最后一位为1的时候n&1=1
            res += n & 1;
            //逐位判断
            n  >>>= 1;
        }
        return res;
    }

    public int hammingWeight(int n) {
        //(n -1) 最右边的1变为0  该数的右边变为1  省略了中间0 的判断
        int res = 0;
        while(n != 0) {
            res++;
            //a & b 同1才1 
            n &= n - 1;
        }
        return res;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年11月9日下午6:28

时间O(logn)
空间O(1)

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //返回n的二进制中1的位数
        // return Integer.bitCount(n);
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
        while(n!=0){
            n = n&(n-1);
            sum++;
        }
        return sum;

}

0 赞同 0 条回复

T 普通 2022年11月9日下午4:46

逐位判断

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

0 赞同 0 条回复

mpweixin用户永久会员 2022年11月9日下午4:45

public class Solution {

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

时间复杂度为O（m) m为1的个数
空间复杂度为O(1)
重点理解为n&n-1

0 赞同 0 条回复

just 普通 2022年11月9日上午11:51

//统计位数
class Solution {
public:
int hammingWeight(uint32_t n) {
int res=0;
for(int i=0;i<32;++i){
int ret=n&(1<<i);
if(ret) res++;
}
return res;
}
};

0 赞同 0 条回复

追普通 2022年11月9日上午10:03

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

每进行一次n & n-1与操作就会使数的最后一位的1变成0
时间复杂度：O(logn)，空间复杂度O（1）

0 赞同 0 条回复

So 普通 2022年11月9日上午9:47

“`java
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int sum = 0;
while (n != 0) {
n = n & (n – 1);
sum++;
}
return sum;
}
}
“`时间：O(log(n))，空间：O(1)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月8日下午11:25

循环检查二进制位

时间复杂度O(k）其中k是int型的二进制位数，k = 32

空间复杂度O(1)

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for(int i = 0;i < 32;i++){
            //和32位上的每一位1相与，计算1的个数
            if((n & (1 << i)) != 0) count++;
        }
        return count;
    }
}

位运算优化

例如 6&(6-1) = 4

6 = (110) 4 = (100) n & (n-1)后能去除最后一位1

时间复杂度O(logn)循环次数等于二进制中1的个数，最坏情况下全部为1，循环logn次

空间复杂度O(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;
            count++;
        }
        return count;
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月8日下午10:40

这道题很简单，移位加与运算统计个数就行
时间复杂度 O(logn)
空间复杂度O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        count=0
        while n!=0:
            if n&1 ==1:
                count=count+1
            n=n>>1
        return count

0 赞同 0 条回复

Error 普通 2022年11月8日下午10:21

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n & 1
            n >>= 1
        return res

时间复杂度 O(n)

0 赞同 0 条回复

青木普通 2022年11月8日下午10:09

/**
    脑残写法，为什么不用循环比对呢
    时间复杂度O(n)
    空间复杂度O(1)
 */
public class Solution {
    // you need to treat n as an unsigned value

    public int hammingWeight(int n) {
        int ans = 0;
        if(n < 0){
            n = n ^ (0b11111111111111111111111111111111);
            ans = -32;
        }
        while(n != 0){
            if((n&1) == 1){
                ans++;
            }
            n = n >> 1;
        }
        return Math.abs(ans);
    }
}

/**
    时间复杂度O(logn)
    空间复杂度O(1)
 */
public class Solution {
    // you need to treat n as an unsigned value

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月8日下午9:41

时间复杂度为O（lgn），空间复杂度为O（1）

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int k = 0;
        while(n != 0){
            n = n & (n-1);
            k++;
        }
        return k;
    }
}

0 赞同 0 条回复

优秀市民普通 2022年11月8日下午8:57

class Solution:
    def hammingWeight(self, n: int) -> int:
        bina = str(bin(n))
        flag = 0
        for i in bina:
            if i == '1':
                flag+=1
        return flag

转为二进制的字符串遍历，时间复杂度on

0 赞同 0 条回复

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

共以下 36 个回答

lowbit 取最低位1

# 回答此问题取消回复

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

共以下 36 个回答

lowbit 取最低位1

# 回答此问题 取消回复

# 回答此问题取消回复