191. Number of 1 Bits
2024-10-15 09:30:15
题目:
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
最新文章
- Redis设计与实现读书笔记(二) 链表
- [课程设计]Scrum 3.4 多鱼点餐系统开发进度(下单详细信息页面&;会员信息页面)
- JQuery基本方法介绍和使用
- android 内存泄露调试
- UINavigationController 与 UITabBarController
- maven编写主代码与测试代码
- filestream.read(buffer,offset,count)的正确解释
- Codeforces#360Div2
- GIT入门笔记(20)- git 开发提交代码过程梳理
- 让自定义view宽高成比例显示
- BZOJ3724PA2014Final Krolestwo——欧拉回路+构造
- bzoj 4464 : [Jsoi2013]旅行时的困惑
- Java命令学习系列(零)——常见命令及Java Dump介绍
- 如何同步两台Linux机器的时间?
- python的Socket网络编程 使用模板
- Linux命令-工作管理命令:&;,ctrl+z,jobs,fg,bg
- Tree通用的系列方法列表-treepanel
- C# 序列化详解,xml序列化,json序列化对比
- 微信小程序 跳坑
- HDU 3172 Virtual Friends(map+并查集)
热门文章
- DigitalOcean(DO)购买VPS流程
- 父节点使用css的transform: translate(0, 0)时position:fixed在chrome浏览器中无效
- mac OS X下PhpStorm+MAMP PRO+Xdebug+FireFox集成开发和断点调试环境配置
- ecshop订单中配送方式报错
- nginx禁止访问某个后缀名的文件
- 爬虫学习之基于Scrapy的爬虫自动登录
- OS/400相关介绍
- IEtester不靠谱
- WPF学习笔记4&mdash;&mdash;Layout之2
- AvalonDock 2.0 的简单运用