191. Number of 1 Bits
2024-03-25 08:29:19
题目：
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
最新文章
- UE4 VR 模式下全屏解决办法
- Homebrew安装
- springMvc文件下载
- iOS搜索框
- linux命令: patch
- js中的json对象
- IIS7.5应用程序池集成模式和经典模式的区别介绍
- 为shell布置陷阱：trap捕捉信号方法论
- 根据HttpServletRequest获取用户真实IP地址
- 稍微记录下Django2.2使用MariaDB和MySQL遇到的坑
- js实现接口隔离
- redis健康检查与故障转移
- 今天碰到一个问题，怎么限制用户在固定宽度的input输入框里输入的长度，由此涉猎到了maxlength属性和size属性以及它们的区别。
- Python字符编码以及循环机制介绍
- RxJS之工具操作符 ( Angular环境 )
- 浅析ARM公司在物联网领域的战略布局
- PAT甲题题解-1017. Queueing at Bank (25)-模拟
- dev richEditControl控件 设置文字 字体 大小
- SQL基于时间的盲注过程
- Android之GPS定位详解