【剑指offer-Java版】10二进制中1的个数

怼烎@ 2022-08-21 08:53 110阅读 0赞

二进制中1的个数：  
思路一：循环右移给定的数，但是存在负数出现死循环的问题  
思路二：声明一个变量flag并初始化为1，然后循环右移flag,循环次数是和给定数的精度也就是位数有关  
思路三：用了二进制一个很有意思的特性：二进制数减少1，那么第一位非零位置会变成0，而该位置右边的零都会变成1。然后将其与原数相与，消除该位右边所有的1(由于减1产生)。循环，直到给定数为0。循环次数就是一个数中1的个数

应用场景：  
1) 可以用来判断一个给定的数是否是2的整数次方，如果一个数是2的整数次方，那么该数值含有一个1，于是将给定数n & (n-1) 结果是0  
2) 求两个二进制数通过改变多少位可以变为对方。那么先将两个数异或运算，得到两个二进制数不同的位数，然互按此题的思路，求出亦或运算的结果中有几个1即可

public class _Q10 {
    
        public int NumberOf1(int n){
    
            int count = 0;
            while(n!=0){
                n = (n - 1) & n;
                count++;
            }
            return count;
        }   
        }

测试代码：

public class _Q10Test extends TestCase {
        
    
        _Q10 numOf1 = new _Q10();
    
        public void testMinInReverse() throws Exception{
            int case1 = 1;
            int case2 = 0x7fffffff;
            int case3 = 0x80000000;
            int case4 = 0xffffffff;
            int case5 = 0;
    
            System.out.println(numOf1.NumberOf1(case1));
            System.out.println(numOf1.NumberOf1(case2));
            System.out.println(numOf1.NumberOf1(case3));
            System.out.println(numOf1.NumberOf1(case4));
            System.out.println(numOf1.NumberOf1(case5));
        }
        }