剑指offer:js实现二进制中1的个数
程序员文章站
2022-07-10 10:25:57
...
题目:给出一个整数,求出这个数转换成二进制中出现1的个数
思路:n&(n-1) 可以消掉末尾的一个1,循环直到0为止
常规解法不应该使用n来作为右移,负数右移0x80000000变成0xC000000
C = 1100 8 = 1000
function f(n){
let i = 0;
while(n!=0){
n = n&(n-1)
i++;
}
return i;
}
延伸:判断一个整数是不是2的整数次方
2的整数次方的二进制只有一个位是1
n&(n-1) == 0 则能判断
延伸2:9个数分别在1-10中,但是缺失了一个数字,找出缺失的这个数
比如5,4,3,6,7,8,9,1,2 缺少了10.
function f(arr,n){
let sum = 0;
arr.forEach(item=>{
sum^=item;
});
let sum2 = 0;
for(let i = 1;i<=n;i++){
sum2 ^= i;
}
return sum^sum2;
}
因为自己和自己异或是0 0和自己异或是本身,所以异或可以解
这题也可以使用累加之后相减也能解决。
延伸3:一个整数数组,有两个整数是奇数个数,其他的个数都是偶数个数 求出这两个奇数个数的数
比如:[1,2,3,1] 2,3个数为奇数个
function f3(arr){
let sum = 0;
arr.forEach(item=>{
sum^=item;
})
let t = sum&(-sum);//n & -n 可以得到右边第一个1
let sum2 = 0;
sum = 0;
arr.forEach(item=>{
if((item&t) == 0){
sum^=item
}else{
sum2^=item
}
})
console.log(sum,sum2);
}
上一篇: shell 字符串截取
下一篇: awk 变量