191. Number of 1 Bits
题目：
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
链接： http://leetcode.com/problems/number-of-1-bits/
题解：
跟上题一样，应该有些很厉害的解法。自己只做了最naive的一种。
Time Complexity - O(1)， Space Complexity - 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++)
if(((n >> i) & 1) == 1)
count++;
return count;
}
}
Brian Kernighan的方法
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
for (count = 0; n != 0; count++) {
n &= n - 1; // clear the least significant bit set
}
return count;
}
}
二刷：
Java:
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++) {
if (((n >> i) & 1) == 1) {
count++;
}
}
return count;
}
}
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;
}
}
三刷:
使用一个while 循环，每次把n的最低的非0位清零。这样比计算全32位计算的位数少，但也多了每次按位与&操作的比较。
Java:
Time Complexity - O(1)， Space Complexity - 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;
}
}
Reference:
http://www.hackersdelight.org/hdcodetxt/pop.c.txt
https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
最新文章
- CI框架使用PHPmail插件发送QQ邮件：
- androi手机解锁引导程序
- java异步式Socket响应数据获取方案
- MySQL Cluster 配置文件(config.ini)详解
- swt小知识点
- Jmeter之逻辑控制器(Logic Controller)
- 有三个线程T1 T2 T3，如何保证他们按顺序执行-转载
- asp.net之ajax
- import了sun开头的类，虽然它在代码里压根就没派上用处！但是必须得引用！
- 关于SQL中的Update语句
- stm32类型cl、vl、xl、ld、md、hd的含义
- 洛谷 P1063 能量项链
- [Boost]boost的时间和日期处理-（2）时间的操作
- UVA 10911 Forming Quiz Teams(dp + 集合最优配对问题)
- 通过扩展改善ASP.NET MVC的验证机制[使用篇]
- ERP小型集团化——运行集团配置向导
- 【曝】苹果应用商店逾千款iOS应用存安全漏洞
- 输入一个数字n 如果n为偶数则除以2，若为奇数则加1或者减1，直到n为1，求最少次数 写出一个函数
- Hadoop记录-queue使用率
- 在SSL / https下托管SignalR