剑指offer(13)——输出二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

一、预先知识点

1 java中的逻辑运算符

• '||' 逻辑或OR,如果任一操作数或两个操作数为true，则结果才是真。只有两个操作数都为假的情况下，输出结果才是假。
• '&&' 逻辑与AND，只有两个操作数都是真，结果才是真。如果第一个是假的话，那么就不在进行第二个操作，返回假。所以，它是一个短路操作。
• '!' 逻辑非。取反

2 java中的位运算符

• '&' 按位与，左右两个数的二进制对应位：全1则1，否则为0
• '|' 按位或，左右两个数的二进制对应位：全0则0，否则为1
• '~' 按位非，右边数的二进制对应位：取反
• '^' 按位异或，左右两个数的二进制对应位：同为0，异为1；与或好像关系不太大

参考链接：
https://blog.csdn.net/emmm_black/article/details/90549807

逻辑与

逻辑或

二、解题思路

1 一个规律

以7作为例子(假设其二进制有八位),0000 0111

现在7-1 = 6，对应的二进制: 0000 0110
再让6与7进行按位与运算，结果为0000 00110，结果是将7最右边的1变为0。

现在总结规律，当一个非零的数减去1，共有两种情况：

第一种，最后一位是1，结果就是最后一位变成0。如7，之前0000 0111,减一之后0000 0110，前后进行按位与，0000 0110
第二种，最后一位不是1，那么这个时候减一，则会使该数的最后边的1变为0，同时之后的所有0都变为1。如6，之前0000 0110,减一之后0000 0101。前后进行按位与，0000 0100

现在让两种情况在减一之前和之后之间进行按位与操作，结果得到数是将原来数的最右边的1变成0。

总结出一般规律就是：把一个数整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0。很多二进制的的问题都可以用这种思路来解决。

2 进行上述一次操作，原来二进制少了一个1，直到最后的结果中没有1。所以，可以统计这个操作可以进行的次数。

package com.justnow.offer;

import java.util.Scanner;

public class Solution13 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solution(n));
    }

    public static int solution(int n) {
        int count = 0;
        while(n!=0) {
            n = n & (n-1);
            count++;
        }
        return count;
    }
}