编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
提示:
-3
。示例 1:
输入:n = 00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。
示例 2:
输入:n = 00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。
示例 3:
输入:n = 11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。
提示:
32
的 二进制串 。进阶:
让原始数据不断左移一位,通过与 1
相&
判断该位是否为1
。
// you need to treat n as an unsigned value
public int hammingWeight(int n)
{
int count = 0;
for (int i = 0; i < 32; i++)
count += (n >> i) & 1;
return count;
}
性质:n & (n - 1)
会使n
的最低位的1
变为0
public int hammingWeight_2(int n)
{
int count = 0;
//循环的执行次数就是 n 的二进制 1 的个数
while(n != 0)
{
n = n & (n - 1);
count++;
}
return count;
}
给你一个整数 n
,对于 0 <= i <= n
中的每个 i
,计算其二进制表示中 1
的个数 ,返回一个长度为 n + 1
的数组 ans
作为答案。
进阶:
O(n log n)
的解决方案,你可以在线性时间复杂度 O(n)
内用一趟扫描解决此问题吗?hammingWeight()
//计算位1的个数
public int hammingWeight(int n)
{
int count = 0;
while(n != 0)
{
n = n & (n - 1);
count++;
}
return count;
}
public int[] countBits(int n)
{
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++)
ans[i] = hammingWeight(i);
return ans;
}
时间复杂度为 O(n log n)
颠倒给定的 32 位无符号整数的二进制位。
示例 1:
输入: 00000010100101000001111010011100
返回: 00111001011110000010100101000000
例如,取n(01001)
的最低位1
单独取出来,左移5 - 1 = 4
位得10000
,将十进制数加入ans
中,此时便将最低位颠倒到了最高位。再更新n
的最低位(每轮右移一位),如此循环,直到n == 0
,便得到颠倒后的十进制数ans
(系统会自动转变为二进制)
注:
>>
会考虑符号位,若符号位为1,则左边补1;若符号位为0,则左边补0。>>>
不考虑符号位,无论原数的符号位是0还是1,左边统一补0。// you need treat n as an unsigned value
public int reverseBits(int n)
{
int ans = 0;
int power = 31;
while (n != 0)
{
ans = ans + ((n & 1) << power);
power--;
n = n >>> 1;
}
return ans;
}
给你两个整数 a
和 b
,不使用 运算符 +
和 -
,计算并返回两整数之和。
面试题 08.05. 递归乘法 - 力扣(LeetCode)
递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
**提示:**保证乘法范围不会溢出
13 * 12
= 13 * (8 + 4)
= 13 * 8 + 13 * 4
= 13 * (1000) + 13 * (0100)
= (13 << 3) + (13 << 2)
public int multiply(int A, int B)
{
int min = Math.min(A, B); //选最小值当乘数能使计算量更少
int max = Math.max(A, B);
int ans = 0;
for (int i = 0; min != 0; i++)
{
if ((min & 1) == 1) //从末位往前取位1
ans += max << i; // max 乘以第一个乘数
min = min >> 1;
}
return ans;
}