10
2
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010,其中有两个1。
-1
32
负数使用补码表示 ,-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111,其中32个1
function NumberOf1(n) { // 从右向左数,找到第一个1,把1后面的所有的数字都变为0 //如x=1000110,x&(x-1)=1000100就是把x右边的第一个1后面的数变为0(包括1) //如果10000的话,结果就是00000了!这样就可以利用这个特性来计算这个十进制书转化为二进制数有多少个1 // write code here //法一: 挪动本身 n.toString(2) let count = 0 for(let i = 0;i<32;i++){ if((n>>>i) & 1){ count++ } } return count }法二: 使用(x-1)&x
function NumberOf1(n) { // 从右向左数,找到第一个1,把1后面的所有的数字都变为0 //如x=1000110,x&(x-1)=1000100就是把x右边的第一个1后面的数变为0(包括1) //如果10000的话,结果就是00000了!这样就可以利用这个特性来计算这个十进制书转化为二进制数有多少个1 //法二: 使用(x-1)&x n.toString(2) let count = 0 while(n!==0){ n = ((n-1)&n) count++ } return count }
function NumberOf1(n) { let num = 0; //最佳方式是位运算,n*(n-1) //例如:n=1010, 1010&1001=1000, 1000&0111=0 while (n != 0) { num++; n = n & (n-1); } return num; } module.exports = { NumberOf1 : NumberOf1 };
/** * 我的解题思路: * 1.首先需要知道JS中通过parseInt(n).toString(2)可以将整数转换成二进制 * 2.对于非负整数转换为二进制之后可以直接遍历获取其中1的个数 * 3.通过补码和反码的知识,我们可以知道二进制负数转换成10进制为(2^32 - 1) - |n| + 1 * 例如-5的二进制为 111...111 1111 - 000...000 0101 = 111...111 1010 + 1 = 111...111 1011 * 4.对于转换后的负数用步骤2获取最终结果 * * @param {*} n */ function NumberOf1(n) { // write code here const m = n >= 0 ? n : Math.pow(2, 32) + n; const str = parseInt(m).toString(2); let i = str.length; let result = 0; while (i--) { str[i] === '1' && result++; } return result; } /** * 评论区TOP的解题思路: * 1.也不知道咋想到的,用与运算去处理 * 2.与运算会对二进制数据进行与处理,及同位均为1得1,否则得0 * 3.n & (n - 1) 可以消除n的二进制数中最右侧的1 * 4.当所有的1都消除时,n = 0,结果即为所求 * * @param {*} n */ function topNumberOf1(n) { // write code here let result = 0; while (n !== 0) { result++; n = n & (n - 1); } return result; }
function NumberOf1(n) { // write code here let num = 0; let value; if(n>=0){ value = n; }else{ value = Math.abs(n+1) } while(value !== 0){ if(value % 2 === 1){ num ++; value = (value-1)/2; }else{ value = value/2; } } if(n>=0){ return num; }else{ return 32 - num; } }
JavaScript
看了很多大佬的讲解,都讲得很透彻,但是看回复发现很多人还是很懵逼,在问“那负数呢?”,“负数怎么办?”等等,都在纠结负数。
其实,要解决这个问题很简单,只需要了解两个常识就ok了。
常识1:在计算机系统中,数值一律用补码来表示和存储。
常识2:正数的原码、反码、补码都是其本身。
也就是说,根本就不需要考虑数的符号问题。
方法一:容易理解,但效率不高,因为根据flag判断循环结束条件,因此,每判断一个数都要循环32次。
function NumberOf1(n) {
var count = 0,
flag = 1;
while (flag != 0) {
if ((n & flag) != 0) {
count++;
}
flag=flag << 1;
}
return count;
}
方法二:效率更高,但是不容易理解,可以看排行第二的大佬 “菩提旭光” 的解释,很透彻。
该方法只需要循环输入整数二进制中1的个数次,相较方法一有了很大提升。
function NumberOf1(n) {
var count = 0;
while (n != 0) {
count++;
n = (n - 1) & n;
}
return count;
}
这是一道考察二进制的题目
二进制或运算符(or):符号为|,表示若两个二进制位都为0,则结果为0,否则为1。
二进制与运算符(and):符号为&,表示若两个二进制位都为1,则结果为1,否则为0。
二进制否运算符(not):符号为~,表示对一个二进制位取反。
异或运算符(xor):符号为^,表示若两个二进制位不相同,则结果为1,否则为0
左移运算符m << n 表示把m左移n位,左移n位的时候,最左边的n位将被丢弃,同时在最右边补上n个0,比如:
00001010<<2 = 00101000
右移运算符m >> n 表示把m右移n位,右移n位的时候,最右边的n位将被丢弃,同时在最左边补上n个0,比如:
00001010>>2 = 00000010
我们可以让目标数字和一个数字做与运算
这个用户比较的数字必须只有一位是1其他位是0,这样就可以知道目标数字的这一位是否为0。
function NumberOf1(n) { let flag = 1; let count = 0; while(flag){ if(flag & n){ count++; } flag = flag << 1; } return count; }
//输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 function NumberOf1(n) { var temp var res = 0 for (var i = 0; i < 32; i++) { //用32位保存 temp = n | 1 //末尾强制为1 if (temp === n) { res++ } n = n >> 1 } return res }
//方法一:不需要理会正负,每次给n减1可以消去二进制表达式最右边的一个1,例如1100&1011=1000,消去了最右边的一个1 function NumberOf1(n) { // write code here var count = 0; while (n != 0) { count++; //n不为0时,总有一位数为1,故不判断与的结果count也可以加1 n = n & n - 1; } return count; } //方法二:负数和情况下>>>右移时高位补0,负数的情况下>>右移高位补1,会造成死循环,所以应该使用>>> function NumberOf1(n) { // write code here var count = 0; while (n != 0) { if (n & 1 == 1) count++; //如果最右边为1,count++,否则继续右移 n = n >>> 1; } return count; }
正数的二进制不需要做过多处理,统计其中的1即可,但是负数的需要经过四步:
1.计算原码,由于Js中负数的二进制已经给出原码了,所以截取一下字符串就可以
2.计算反码,将每一位翻转即可
3.计算补码,满二进1即可
4.计算补码中1的个数
function NumberOf1(n) {
var sum = 0;
if(n > 0) {//正数的直接获取即可
var binary = n.toString(2);
var binaryArr = binary.split("");
binaryArr.forEach(function(item) {
if(item === '1') {
sum++;
}
})
}
else {
var binary = n.toString(2);//得到一个负号加上绝对值的原码
var origin = binary.substring(1);//截取原码
var reverse = getReverse(origin);//获取反码
reverse[0] = 1;//因为是负数,所以符号位应该是1
var complement = getComplement(reverse);//获取补码
var arr = complement.split("");
arr.forEach(function(item) {
if(item === '1') {
sum++;
}
})
}
return sum;
}
function getComplement(reverse) {
var arr = reverse.split("");
var add = 1;
for(var i = arr.length - 1; i >= 0; i--) {
if(parseInt(arr[i]) + add == 1) {
arr[i] = 1;
add = 0;
}
if(parseInt(arr[i]) + add >= 2) {
arr[i] = 0;
add = 1;
}
else {
add = 0;
}
}
return arr.join('');
}
function getReverse(origin) {
var len = origin.length;
origin = Array(33-len).join('0')+(origin).toString(2);
var reverse = '';
origin.split("").forEach(function(item) {
if(item === '1') {
reverse += '0';
}
else {
reverse += '1';
}
})
return reverse;
}
// 负整数的补码的反码就是负整数按位非(~)的结果 // 负整数的补码:对应正整数的补码按位取反,末位加1 function NumberOf1(n) { var count = 0; var numberArr = []; var tmpArr = []; if (n >= 0) { numberArr = n.toString(2).split(''); } else { tmpArr = (Array(33).join(0) + (~n).toString(2)).slice(-32).split(''); // 得到负整数按位非(~)的32位结果数组 numberArr = tmpArr.map((val) => 1^val); // 按位取反 } numberArr.forEach((val) => { if (val === 1 || val === '1') { count++; } }); return count; }