11 剑指offer--位运算--二进制中1的个数
二进制中1的个数
public class Solution {
public int NumberOf1(int n) {
int index =0;
while(n != 0){
n = (n-1)&n;
++index;
}
return index;
}
}基础知识
位运算是把数字用二进制表示之后，对每一位上0 或 者 I 的运算。二进制及其位运算是现代计算机学科的基石，很多底层的技术都离不开位运算，因此与位运算相关的题目也经常出现在面试中。我们在日常生活中习惯了十进制，很多人看到二进制及位运算都觉得很难适应。
理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者I。比如十进制的2 转换成二进制之后是10,而十进制的10转换成二进制之后是1010。在程序员圈子里有一则流传了很久的笑话，说世界上有10种人，一种人知道二进制，而另一种人不知道二进制 ...
在微软产品Excel中，用 A 表示第1 列，B 表示第2 列……Z 表示第26列，AA表示第27列，AB表示第28列……以此类推。请写出一个函数，输入用字母表示的列号编码，输出它是第几列。
这是一道很新颖的关于进制的题目，其本质是把十进制数字用A〜Z表示成二十六进制。如果想到这一点，那么解决这个问题就不难了。其实二进制的位运算并不是很难掌握，因为位运算总共只有5 种运算:与、或、异或、左移和右移。与、或和异或运算的规律我们可以用表2.1总结如下。
把 一 个 整 数 减 去 1 之 后 再 和 原 来 的 整 数 做 位 与 运 算 ，得到的结果相当于把整 数的二进制表示中最右边的1变成0 很多二进制的问题都可以用这种 思 路 解 决 ，
左移和右移
左移运算符 m << n 表示把 m 左移 n 位。在左移n 位的时候，最左边的 n位将被丢弃，同时在最右边补上n个 0.比如：
00001010<<2=00101000
10001010<<3=01010000
右移运算符m>>n表示把m右移n位。在右移n位的时候,最右边的。
n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值,则用0填补最左边的n位;如果数字是一个有符号数值,则用数字的符号位填补最左边的n位。也就是说,如果数字原先是一个正数,则右移之后在最左边补n个0:如数字原先是负数,则右移之后在最左边补n个1下面是对两个8位有符号数进行右移的例子:
00001010>>2=00000010
10001010>>3=11110001
1、基本都是参考别的博客和书本的代码,仅作为自己笔记用!!
1、<<:左移运算符,num<<1相当于num乘以2
>>:右移运算符,num>>1,相当于num除以2
>>>:无符号右移,忽略符号位,空位都以0补齐
2、与1位与得1就是奇数,1只有最后一位是1
题目
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路：最简单的思路，整数n每次进行无符号右移一位，同1做&运算，可以判断最后以为是否为1。
通常的剑指offer的思路，n&(n-1) 操作相当于把二进制表示中最右边的1变成0。所以只需要看看进行了多少次这样的操作即可。看看什么时候n为0.
思路1：
先判断二进制表示的最右1位是不是1，把整数和1做与运算即可，然后右移一位，再判断，直到整数变为0。
把整数右移一位和把整数除以2在数学上是等价的但是位运算效率最高，但是思路1可能会陷入死循环，如输入一个负数0x8000，右移之后并不是0x4000，而是0xC000，因为负数移位后要补1，如果循环下去会变成0xFFFF。
思路2：
为了避免死循环就要避免右移，我们首先把数字和1做与运算，判断它最低位是不是1，接着把1左移一位得到2，在和输入数与运算，节能判断次低位是不是1，反复左移即可。
#include<iostream>
using namespace std;
int NumberOf1(int n)//有符号的n
{
int count=0;
int flag=1;
while (flag)
{
if (n&flag)
{
count++;
}
flag=flag<<1;//左移一位
}
return count;
}
int main()
{
cout<<NumberOf1(9)<<endl;//1001
cout<<NumberOf1(15)<<endl;//1111
return 0;
}
思路3
思路2中输入的数的二进制表示有几位，程序就会循环多少次，改进的思路3是二进制里有几个1就循环几次。首先记住一个常用做法：把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数二进制表示中的最右边一个1变成0。基于上述做法，一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。
public class NumberOf1 {
static Integer numberof1(int number){
int count = 0;
while(number != 0){
number = (number - 1) & number;
count++;
}
return count;
}
public static void main(String[] args){
System.out.println(numberof1(10));
}
}
LeetCode
位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 ***有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 ***有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 ***有 31 位为 '1'。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
进阶:
如果多次调用这个函数，你将如何优化你的算法？
public static void main(String[] args) {
System.out.println("请输入一个整数");
Scanner sc = new Scanner(System.in);
System.out.println(sc.nextInt());
}
public static int hammingWeight(int n) {
int num =0;
String s = Integer.toBinaryString(n);
for (int i = 0; i <s.length() ; i++) {
if(s.charAt(i) =='1'){
++num;
}
}
return num;
}
相关问题
判断一个整数是不是2的整数次方
分析：一个整数如果是2的正数次方，那么这个正数的二进制位中只有一个1；
只需要一句语句就可以判断：假设这个正数为n:只需判断n&(n-1)是否为0；
#include<iostream>
using namespace std;
bool fun(int n)
{
if (n&n-1)
{
return false;
}
return true;
}
int main()
{
cout<<fun(1)<<endl;
cout<<fun(2)<<endl;
cout<<fun(8)<<endl;
cout<<fun(10)<<endl;
return 0;
}
输入两个整数m和n,计算需要改变m二进制中的多少位才能得到n;
如：10:1010；13:1101，则需要改变10的二进制的后三位才能得到1101；
解决思路是，先求这两个数的异或，然后统计异或结果中1的个数。
public class NumberOf1 {
static Integer numberof1(int number){
int count = 0;
while(number != 0){
number = (number - 1) & number;
count++;
}
return count;
}
public static void main(String[] args){
System.out.println(numberof1(10));
}
}
