c语言中把一个数缩小十倍_【动漫】作业帮面试题：求一个数的二进制中1的个数...

小夕&＃xff1a;我先来说一下我的解法&＃xff1a;

• 1、先将数字转换成二进制字符串
• 2、用String.split()函数存入一个数组中
• 3、遍历数组跟1比较&＃xff0c;同时计数
• 4、输出计数值


public class Solution { 
    public int NumberOf1(int n) { 
        String s&＃61;Integer.toBinaryString(n); 
        String[] split&＃61;s.split(""); 
        int a&＃61;0; 
        for(int i &＃61; 0; i             if (split[i].equals("1")) 
           { a&＃43;&＃43;; }
        } 
        return a; 
    } 
}



助教&＃xff1a;对于一个数12&＃xff0c;求它的二进制中有几个1。count代表它里面有几个1。然后我将n和n-1的按位相与&＃xff1a;

n是12&＃xff0c;n-1是11&＃xff0c;两者按位相与&＃xff0c;n&n-1 &＃61; 8&＃xff0c;n&n-1 它的二进制是1000。

到这里我们发现减1的结果是把最右边的一个1开始的所有位都取反了。也就是下图所示&＃xff0c;全都取反了&＃xff01;这个时候如果我们再把原来的整数和减去1之后的结果做与运算(也就是n&n-1)&＃xff0c;从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011&＃61;1000。也就是如下图所示&＃xff1a;也就是说&＃xff0c;把一个整数减去1&＃xff0c;再和原整数做与运算(也就是n&n-1)&＃xff0c;会把该整数最右边一个1变成0.也就是如下图所示&＃xff0c;n&＃61;12变成了n&n-1也就是变成8,12是1100,8是1000&＃xff0c;12的二进制中最右边的1变成了0也就是成为了8。那么一个整数的二进制有多少个1&＃xff0c;就可以进行多少次这样的操作。好的接下来&＃xff0c;让n&＃61;n&n-1,也就是n&＃61;8了&＃xff0c;那么n-1是7&＃xff0c;来继续求n&n-1。n继续和n-1按位相与得到的结果是0&＃xff1a;最后由于结果为0&＃xff0c;所以结束&＃xff0c;一共进行了两次这样的操作&＃xff0c;所以12二进制中有两个1。

Java

public class Solution {
    public int NumberOf1(int n) {
        int count &＃61; 0;
        while (n !&＃61; 0) {
            &＃43;&＃43;count;
            n &＃61; (n - 1) & n;
        }
        return count;
    }
}


Python

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count &＃61; 0;
        if n 0:
            n &＃61; n & 0xffffffff
        while (n !&＃61; 0):
            count &＃43;&＃61; 1
            n &＃61; (n - 1) & n
        return count;


C&＃43;&＃43;

class Solution {
public:
     int  NumberOf1(int n) {
        int count &＃61; 0;
        while (n !&＃61; 0) {
            &＃43;&＃43;count;
            n &＃61; (n - 1) & n;
        }
        return count;
     }
};


PHP

     $count &＃61; 0;if($n 0){ // 处理负数
       $n &＃61; $n&0x7FFFFFFF;
       &＃43;&＃43;$count;
     }
     while($n !&＃61; 0){
      $count&＃43;&＃43;;
      $n &＃61; $n & ($n-1);
     }
     return $count;
}


JS

function NumberOf1(n){
    // write code here
    var count &＃61; 0;
    while (n !&＃61; 0) {
        count&＃43;&＃43;;
        n &＃61; (n - 1) & n;
    }
    return count;
}


【助教解释一下】n &＃61; n & 0xffffffff&＃xff0c;在Python中&＃xff0c;数的大小是可以无限扩大的&＃xff0c;不会像Java或c&＃43;&＃43;中&＃xff0c;数超过32位会溢出&＃xff0c;而是继续扩张&＃xff0c;所以对于一个负数而言&＃xff0c;进行了这个操作&＃xff0c;实际上是提取了负数的后32位(在计算机中以补码形式存在)&＃xff0c;前面的任意位呢&＃xff0c;则变成了0&＃xff0c;比如说 -1&＃xff0c;一开始是 111.....(n个1)...11111111&＃xff0c;进行与运算之后&＃xff0c;得到&＃xff0c;00....(n个0)....111111111(32个1)&＃xff0c;变成了含32个1的正数&＃xff0c;然后就不用担心负数陷入死循环。

如果大家觉得文章不错&＃xff0c;不妨点赞(在看)、转发支持一下小夕&＃xff01;冲鸭&＃xff01;我们下周再见。原创能坚持下去真的很难&＃xff0c;各位的在看和转发真的是我的唯一动力了&＃xff0c;不要让小夕放弃呀~~~