Title Description:

Input an integer and output the number of 1 in the binary representation of that number. Negative numbers are represented by complements.

Solution 1: Idea analysis:

step 1: num binary rightmost bit and 1 phase, if not 0, count plus 1;

step 2: Otherwise, move one bit to the left and continue to phase with the second bit of the rightmost binary number of num.

step 3: Cycle in turn, you can complete.

Solution 1 code implementation:

import java.util.Scanner;
public class Exercise18 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int num = sc.nextInt();
            int count = NumberOf1(num);
            System.out.println(count);
        }
    }

    private static int NumberOf1(int num) {
        //Judging whether num is zero
        if(num == 0){
            return 0;
        }
        //Number of occurrences of record 1
        int count = 0;
        int flag = 1;
        //flag moves to the left, and when it reaches 10000000000000, if it moves to the left, it goes back to 0.
        while(flag != 0){
            //num may be a negative number. When it is in phase with flag, the result is less than 0.
            //So as long as the results of the two are not zero.
            if((num & flag) != 0){
                count++;
            }
            //flag moved one bit to the left
            flag = flag << 1;
        }
        return count;
    }

}

Solution 1 Defect analysis:

The number of iterations is more, the number of iterations of solution 1 code is related to the data type. If it is int type (4 bytes), then it stores 32 bits in the computer. If it is short type (2 bytes), then it stores 16 bits in the computer. If the data does not occupy the whole bit bit bit, even if I get it. The result we want is that flag moves left until flag is 0. In other words, no matter how big it is, flag moves 32 bits left, that is, 32 cycles. For short data, flag moves 16 bits left, that is, 16 cycles.

 

Solution 2: Idea analysis:

step 1: num binary and 1 phase, if not 0, count plus 1;

step 2: Otherwise, move num one bit unsigned to the right and continue to phase with 1.

step 3: Cycle in turn, you can complete.

Solution 2 code implementation:

import java.util.Scanner;
public class Exercise18 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int num = sc.nextInt();
            int count = NumberOf2(num);
            System.out.println(count);
        }
    }

    private static int NumberOf2(int num) {
        //Judging whether num is zero
        if(num == 0){
            return 0;
        }
        //Number of occurrences of record 1
        int count = 0;
        int flag = 1;
        while(num != 0){
            //num may be a negative number. When it is in phase with flag, the result is less than 0.
            //So as long as the results of the two are not zero.
            if((num & flag) != 0){
                count++;
            }
            //num moves one bit unsigned to the right. If it is changed to the signed to the right, the positive number will not affect, and the negative number will cause the system to fall into a dead cycle.
            num = num >>> 1;
        }
        return count;
    }

Solution 2 Defect analysis:

(1) For solution 2, if you do not pay attention to writing the code as a signed right shift, i.e. num = num > > > 1, the num you get is just a negative number (negative number, when you move right, the highest bit will be complemented, no matter how many times you move right, there will always be one of the 1-symbol bits, which will result in one at this time. Negative numbers get innumerable numbers of 1, which will cause the system to fall into a dead cycle.

(2) The original number has been changed, which is not conducive to later use.

 

Solution 3:

step 1: If an integer is not zero, then at least one of the binary digits of the integer is 1;

step 2: If we subtract this integer by 1, then the 1 on the rightmost side of the integer will become 0, and all the 0 after 1 will become 1 (if there is 0 after the rightmost 1), and the remaining digits before the 1 (1 becomes 0) after the change will not be affected;

step 3: num and num - 1 phase and eliminate the rightmost 1 of the binary bit of the number;

step 4: Cycle in turn, you can complete.

Solution 3 code implementation:

import java.util.Scanner;
public class Exercise18 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int num = sc.nextInt();
            int count = NumberOf3(num);
            System.out.println(count);
        }
    }

    private static int NumberOf3(int num) {
        //Judging whether num is zero
        if(num == 0){
            return 0;
        }
        //Number of occurrences of record 1
        int count = 0;
        //When num is not zero, the binary of any other integer has at least one 1. After entering the loop, count adds 1 first.
        while(num != 0){
            count++;
            /**
             * num-1，If the first bit of the binary right-hand digit of n is 1, then it becomes 0. If only a few digits are 1,
             * For example: 0110 0100, the rightmost 1 becomes 0.
             * The 00 on the right side of the original 1 changes to 11, 0110 0011, and then to num.
             * The value is 0110,000,000, (just eliminating the one on the rightmost side)
             * Ultimately, num & (num - 1) will only change the rightmost 1 to 0
             */
            num = num & (num - 1);
        }
        return count;
    }

Solution 3 Defect Analysis:

The original number has been changed, which is not conducive to later use.

 

Topic Summary:

(1) Solution 1 has more cycles, but does not change the original data.

(2) Solution 2 changes the original data. If the code is written as a signed right shift, for negative numbers, it will cause a dead cycle of the system.

(3) Solution 3 changed the original data.

 

The storage form of the number in the computer:

https://mp.csdn.net/postedit/98472451

Java Shift Operator:

https://mp.csdn.net/postedit/98472473

Spiritual chicken soup: consider a thousand times, do it once; hesitate 10,000 times, practice once; gorgeous fall, better than meaningless hesitation, in the future you will thank yourself for the struggle now.