wordpress打开网页慢,seo顾问服务公司,中山营销网站建设费用,在线设计平台行业的发展趋势经典题目#xff0c;位操作的小技巧#xff1a;与操作
我们可以把前面的算法进行优化。我们不再检查数字的每一个位#xff0c;而是不断把数字最后一个 1 反转#xff0c;并把答案加一。当数字变成 00 的时候偶#xff0c;我们就知道它没有 1 的位了#xff0c;此时返回… 经典题目位操作的小技巧与操作
我们可以把前面的算法进行优化。我们不再检查数字的每一个位而是不断把数字最后一个 1 反转并把答案加一。当数字变成 00 的时候偶我们就知道它没有 1 的位了此时返回答案。
这里关键的想法是对于任意数字 n 将 n 和 n - 1做与运算会把最后一个 1的位变成 0 。为什么考虑 n和 n - 1的二进制表示。 在二进制表示中数字 n 中最低位的 1 总是对应 n - 1中的 0。因此将 n和 n−1 与运算总是能把 n 中最低位的 1 变成 0 并保持其他位不变。
public class Solution
{public int HammingWeight(uint n){int sum 0;while (n ! 0) {sum;n (n - 1);}return sum;}
}
复杂度分析
时间复杂度O(1)。运行时间与 n 中位为 1 的有关。在最坏情况下 n 中所有位都是 1 。对于 32 位整数运行时间是 O(1) 的。
空间复杂度O(1)。没有使用额外空间。
