Write a function that takes
an unsigned integer and returns the number of ’1' bits it has (also known as
the Hamming weight).
For example, the 32-bit
integer ’11' has binary representation
00000000000000000000000000001011
so the function should
return 3.
Напишите функцию, которая в
беззнаковом целом числе вычисляет количество 1-битов (вес Хемминга).
Например, в 32-битовом
целом числе ’11', имеющем бинарное представление
00000000000000000000000000001011
имеется три единичных бита.
Функция должна вернуть 3.
// C++
class Solution {
public:
int hammingWeight(uint32_t n) {
}
};
// Java
public class
Solution {
// you need to treat n as an unsigned value
public int
hammingWeight(int n) {
}
}
циклы
Подсчитываем количество
единиц в двоичном представлении числа n. Число n является беззнаковым целым, на вход может подаваться
n = 2147483648 (или в двоичном 10000000000000000000000000000000)
Реализация алгоритма
class Solution
{
public:
int hammingWeight(uint32_t n)
//int
hammingWeight(unsigned int n)
{
int res = 0;
В цикле делим n на 2 пока n > 0. Подсчитываем сумму битов.
while(n > 0)
{
res = res + n %
2;
n /= 2;
}
return res;
}
};
Java реализация
public class Solution
{
// you need to treat n as an unsigned value
public int
hammingWeight(int n)
{
int res = 0;
for(int i = 0; i <
32; i++)
{
res = res + (n
& 1);
n = n >> 1;
}
return res;
}
}
Java реализация – вторая версия
Операция n = n & (n – 1) удаляет последнюю 1 в двоичном представлениии числа n независимо от ого является
ли n положительным или
отрицательным.
public class Solution
{
// you need to treat n as an unsigned value
public int hammingWeight(int n)
{
int res = 0;
while(n != 0)
{
n = n &
(n-1);
res++;
}
return res;
}
}