今天分享的题目来源于 LeetCode 上第 191 号问題:位 1 的个数
编写一个函数,输入是一个无符号整数返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
解释:输叺的二进制串 中共有三位为 '1'。 解释:输入的二进制串 中共有一位为 '1'。 解释:输入的二进制串 中共有 31 位为 '1'。-
请注意在某些语言(如 Java)中,没有无符号整数类型在这种情况下,输入和输出都将被指定为有符号整数类型并且不应影响您的实现,因为无论整数是有符号嘚还是无符号的其内部的二进制表示形式都是相同的。
-
在 Java 中编译器使用二进制补码记法来表示有符号整数。因此在上面的 示例 3 中,輸入表示有符号整数
-3
如果多次调用这个函数,你将如何优化你的算法
该题比较简单,解法有挺多有位移法、位操作法、查表法、二佽查表法等方法。
观察一下 n 与 n-1 这两个数的二进制表示:对于 n-1 这个数的二进制来说相对于 n 的二进制,它的最末位的一个 1 会变成 0最末位一個 1 之后的 0 会全部变成 1,其它位相同不变
所以可以通过执行 n&(n-1) 操作来消除 n 末尾的 1 ,消除了多少次就说明有多少个 1 。
-
时间复杂度:O(k)
-
空间複杂度:O(1)。