【Offer】[15] 【二进制中1的个数】
2024-09-01 06:24:10
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路分析
- 让整数和
1相与，可以判断整数二进制表示中最右边一位是否为1，将1左移之后再和整数相与，可以比较右数第二位，循环比较，就可以统计出二进制中1的个数
（可能一般想到的是将整数右移，之后再和1相与，但是这种方法传入负数时会陷入死循环，因为负数的右移操作会在高位补1，而不是0） - 一个整数减去1之后再和原来的整数相与，那么整数二进制中最右边的1会变为0，直到整数变为0，就可以统计出1的个数。
- 2中的规律还有如下应用：
- 用一条语句判断一个整数是否是2的整数次方（如果一个整数是2的整数次方，那么它的二进制表示当中只有一个1，其余位都为0）
- 输入两个整数m和n，计算m需要改变m的二进制中表示的多少位才能得到n，（先将m和你进行异或操作，那么就变成了这个题目）
测试用例
- 正数（包括边界值1、0x7FFFFFFF）
- 负数（包括边界值0x80000000、0xFFFFFFFF）
- 0
Java代码
public class Offer15 {
public static void main(String[] args) {
System.out.println("测试正数-->");
test1();
System.out.println("测试负数-->");
test2();
System.out.println("测试0-->");
test3();
}
public static int NumberOf1(int n) {
return Solution3(n);
}
/**
* 解法一： 思路： 上面的思路是移动 整数，我们可以移动与整数相与的1 ，每次判断之后我们将1 向左移动， 这时判断的就是整数所表示二进制中右边的第二位
*
* @param n
* @return
*/
private static int Solution2(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((flag & n) != 0) {
count++;
}
flag = flag << 1;
}
return count;
}
/**
* 解法二： 思路 ：利用了一种二进制运算的规律，把一个整数减去1之后再和原来的整数做与运算， 得到的结果相当于把整数二进制中最右边的1变为0
*
* @param n
* @return
*/
private static int Solution3(int n) {
int count = 0;
while (n != 0) {
count++;
n = n & (n - 1);
}
return count;
}
/**
* 测试正数
*/
private static void test1() {
System.out.println("0x7FFFFFFF: " + NumberOf1(0x7FFFFFFF));
System.out.println("1: " + NumberOf1(1));
}
/**
* 测试负数
*/
private static void test2() {
System.out.println("0x80000000： " + NumberOf1(0x80000000));
System.out.println("0xFFFFFFFF： " + NumberOf1(0xFFFFFFFF));
}
/**
* 测试0
*/
private static void test3() {
System.out.println("0: " + NumberOf1(0));
}
}
代码链接
最新文章
- APP多版本共存，服务端如何兼容？
- Material Design 概念,环境和基本属性
- ajax给全局变量赋值问题解决示例
- for-in遍历json数据
- CI 中css样式或者js样式加载不进来的情况
- [译]Stairway to Integration Services Level 5 - 增量删除数据
- polling轮询和comet
- (简单) HDU 2612 Find a way，BFS。
- awakeFromNib与initWithCoder
- smarty的学习计划（1）
- Objective-C Runtime 文档翻译
- Mock接口平台Moco学习
- murri
- 在Linux上编译Hadoop-2.4.0实践与总结
- 洛谷 P1110 [ZJOI2007]报表统计 解题报告
- java json Gson
- 如何做好错误处理？（PHP篇）
- GO入门——1.基础
- JNDI的学习与使用
- Java基础知识学习笔记（一）