15-二进制中1的个数

题目描述

https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量).）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3中，输入表示有符号整数 -3。

示例 1：

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011中，共有三位为 '1'。

示例 2：

输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000中，共有一位为 '1'。

示例 3：

输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

输入必须是长度为 32 的二进制串。

注意：本题与主站 191 题相同：https://leetcode.cn/problems/number-of-1-bits/

思路分析

基本思路：单数(二进制最后一个为1)和 1 做 & 运算就是1，双数(二进制最后一个为0) 和1 做 & 运算就为0

实现代码

csharp

public class Solution {
    // 基本思路：单数(二进制最后一个为1)和 1 做 & 运算 就是1， 双数(二进制最后一个为0) 和1 做 & 运算就为0 
    // 运算一次后，将改数右移1位，直至为0
    public int HammingWeight(uint n) {
        int result = 0;
        while(n > 0){
            result += (int)(n & 0x1);
            n = n >> 1;
        }
        return result;
    }
}

实现代码2

csharp

// 将 n-1 和 n 相与，这样可以减少计算次数
// 比如 1001 ， 先减去1可以自己相遇 1001 & 1000 = 1000, 然后再 1000 & 0111 = 0 ，这样计算两次就可以得到结果值为2，不需要位移四次。 

public class Solution {
    public int HammingWeight(uint n) {
        int count = 0;
        while(n > 0){
            n = n & (n-1);
            count ++;
        }
        return count;
    }
}

补充知识

按位与 & 0&0=0，0&1=0，1&0=0，1&1=1
按位或 | 0|0=0，0|1=1，1|0=1，1|1=1
异或 ^ 0^0=0，0^1=1，1^0=1，1^1=0
取反 ~ ~0 = 1 , ~1 = 0
左移运算符 << 用来将一个数的各二进位全部左移若干位，右补0，高位左移后溢出，舍弃不起作用。左移一位相当于乘以2
右移运算符 >> 用来将一个数的各二进位全部右移若干位，移到右端的低位被舍弃，对无符号数，高位补0；右移一位相当于除以2
- 对有符号数，左边移入0（“逻辑右移”）或1（“算术右移”）
- C#, C语言是用的补码方式(取反+1)表示的如 -9 -> 11111111111111111111111111110111 ，右移一位为 11111111111111111111111111111011 等于 -5
- C#,C语言使用的是算术右移

15-二进制中1的个数 #

题目描述 #

思路分析 #

实现代码 #

实现代码2 #

补充知识 #