Напишите алгоритм, чтобы найти F(n) количество бит, установленное в 1, во всех числах от 1 до n для любого заданного значения n.
Сложность должна быть O(log n)
Например:
1: 001
2: 010
3: 011
4: 100
5: 101
6: 110
Итак,
F(1) = 1,
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.
Я могу только разработать алгоритм O(n).
Способ решения этих проблем состоит в том, чтобы записать первые несколько значений и искать шаблон
Number binary # bits set F(n) 1 0001 1 1 2 0010 1 2 3 0011 2 4 4 0100 1 5 5 0101 2 7 6 0110 2 9 7 0111 3 12 8 1000 1 13 9 1001 2 15 10 1010 2 17 11 1011 3 20 12 1100 2 22 13 1101 3 25 14 1110 3 28 15 1111 4 32
Требуется немного взглянуть, но, с некоторыми соображениями, вы заметили, что двоичные представления первых 8 и последних 8 чисел точно такие же, за исключением того, что первые 8 имеют 0 в MSB (большинство значащий бит), а последние 8 имеют 1. Таким образом, например, чтобы вычислить F(12), мы можем просто взять F(7) и добавить к нему число установленных бит в 8, 9, 10, 11 и 12. Но это то же самое, что и число битов в 0, 1, 2, 3 и 4 (т.е. F(4)), плюс еще один для каждого числа!
# binary 0 0 000 1 0 001 2 0 010 3 0 011 4 0 100 5 0 101 6 0 110 7 0 111 8 1 000 <--Notice that rightmost-bits repeat themselves 9 1 001 except now we have an extra '1' in every number! 10 1 010 11 1 011 12 1 100
Таким образом, для 8 <= n <= 15, F(n) = F(7) + F(n-8) + (n-7). Аналогично можно было бы отметить, что для 4 <= n <= 7, F(n) = F(3) + F(n-4) + (n-3); и для 2 <= n <= 3, F(n) = F(1) + F(n-2) + (n-1). В общем случае, если положить a = 2^(floor(log(n))), то F(n) = F(a-1) + F(n-a) + (n-a+1)
Это не совсем дает нам алгоритм O(log n); однако делать это легко. Если a = 2^x, то обратите внимание на приведенную выше таблицу, что для a-1 первый бит устанавливается ровно a/2 раз, второй бит устанавливается ровно a/2 раз, третий бит... полностью до x'th бит. Таким образом, F(a-1) = x*a/2 = x*2^(x-1). В приведенном выше уравнении это дает нам
F(n) = x*2x-1 + F(n-2x) + (n-2x+1)
Где x = floor(log(n)). Каждая итерация вычисления F существенно удалит MSB; таким образом, это алгоритм O(log(n)).
Если n= 2^k-1, then F(n)=k*(n+1)/2
Для общего n пусть m - наибольшее число такое, что m = 2^k-1 и m<=n. F(n) = F(m) + F(n-m-1) + (n-m).
Условие угла: F(0)=0 и F(-1)=0.
рассмотрим ниже:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Если вы хотите найти общее количество заданных бит от 1 до 14 (1110) Несколько наблюдений:
0th бит (LSB) 1 отображается один раз каждые два бита (см. вертикально), так что количество установленных бит = n/2 + (1, если n 0th bit is 1 else 0)1st бит position = (n/4 *2) + 1 (так как бит 1st - это set, else 0)2nd бит: 4 последовательный 1s появляется каждый бит 8 (этот бит немного сложнее)
количество заданных битов во 2-й позиции = (n/8*4 )+ 1 (поскольку бит 2nd установлен, else 0) + ((n%8)%(8/2))
Последний член должен включать число 1s, которые были вне первой группы (n/8) бит (14/8 =1 учитывает только группу 1, т.е. 4 устанавливает биты в битах 8. Мы должны включить 1s найдено в последних 14-8 = 6 битах)3rd бит: 8 последовательные 1s появляются каждый бит 16 (аналогично выше)
количество установленных бит в 3rd position = (n/16*8)+1 (поскольку бит 3rd установлен, else 0) + ((n%16)%(16/2)) поэтому мы делаем вычисление O(1) для каждого бита числа n.
число содержит бит log2(n). поэтому, когда мы повторяем вышеперечисленное для всех позиций n и добавляем все установленные биты на каждом шаге, мы получаем ответ в шагах O(logn)
Быстрый поиск значений последовательности F приводит к этой целочисленной последовательности http://oeis.org/A000788
Там я заметил формулу: a (0) = 0, a (2n) = a (n) + a (n-1) + n, a (2n + 1) = 2a (n) + n + 1 (a совпадает с F, так как я просто скопируйте формулу из oeis)
который может быть использован для вычисления a (n) в log (n).
Вот мой пример кода на С++:
memset(cache, -1, sizeof(cache))
cache[0] = 0
int f(int n)
if cache[n] != -1 return cache[n];
cache[n] = n % 2 ? (2 * f(n / 2) + n / 2 + 1) : (f(n / 2) + f(n / 2 - 1) + n / 2)
Вот мое решение этого. Временная сложность: O (Log n)
public int countSetBits(int n){
int count=0;
while(n>0){
int i= (int)(Math.log10(n)/Math.log10(2));
count+= Math.pow(2, i-1)*i;
count+= n-Math.pow(2, i)+1;
n-= Math.pow(2, i);
}
return count;
}
Пусть k - количество бит, необходимое для n.
для 0,...,2^(k-1)-1 каждый бит равен ровно для половины чисел, поэтому мы до сих пор биты (k-1)*2^(k-1)/2 = (k-1)*2^(k-2). Нам нужно только проверить, чем больше цифры, чем 2^(k-1)-1
Мы также имеем для этих n-2^(k-1)-1 бит "вверх" для MSB.
Таким образом, мы можем получить рекурсивную функцию:
f(n) = (k-1)*2^(k-2) + n-(2^(k-1)-1) + f(n-(2^(k-1)))
^ ^ ^
first MSBs recursive call for
2^(k-1)-1 n-2^(k-1) highest numbers
numbers
Где база f(0) = 0 и f(2^k) = k*2^(k-1) + 1 [как мы видели раньше, мы точно знаем, сколько бит для 2^(k-1)-1, и нам просто нужно добавить 1 - для MSB 2^k]
Так как значение, отправленное на f, уменьшается на минимум на каждую итерацию, мы получаем общее количество O(logn)
короткий и сладкий!
public static int countbits(int num){
int count=0, n;
while(num > 0){
n=0;
while(num >= 1<<(n+1))
n++;
num -= 1<<n;
count += (num + 1 + (1<<(n-1))*n);
}
return count;
}//countbis
Вот java-функция
private static int[] findx(int i) {
//find the biggest power of two number that is smaller than i
int c = 0;
int pow2 = 1;
while((pow2<< 1) <= i) {
c++;
pow2 = pow2 << 1;
}
return new int[] {c, pow2};
}
public static int TotalBits2(int number) {
if(number == 0) {
return 0;
}
int[] xAndPow = findx(number);
int x = xAndPow[0];
return x*(xAndPow[1] >> 1) + TotalBits2(number - xAndPow[1]) + number - xAndPow[1] + 1;
}
это закодировано в java...
логика: говорят, что число равно 34, двоичный равен ant равен 10010, который может быть записан как 10000 + 10.
10000 имеет 4 нуля, поэтому количество всех 1 до этого числа составляет 2 ^ 4 (причина ниже). поэтому счет равен 2 ^ 4 + 2 ^ 1 + 1 (номер его сам). поэтому ответ 35.
* для двоичного числа 10000. Общие комбинации заполнения 4 места составляют 2 * 2 * 2 * 2x2 (один или ноль). Таким образом, суммарные комбинации из них 2 * 2 * 2 * 2.
public static int getOnesCount(int number) {
String binary = Integer.toBinaryString(number);
return getOnesCount(binary);
}
private static int getOnesCount(String binary) {
int i = binary.length();
if (i>0 && binary.charAt(0) == '1') {
return gePowerof2(i) + getOnesCount(binary.substring(1));
}else if(i==0)
return 1;
else
return getOnesCount(binary.substring(1));
}
//can be replaced with any default power function
private static int gePowerof2(int i){
int count = 1;
while(i>1){
count*=2;
i--;
}
return count;
}
Кстати, этот вопрос также может быть сделан методом таблицы поиска. Предварительно сравните количество заданных бит с 0-255 и сохраните его. Положите, что мы можем вычислить количество заданных бит в любом числе, разбив заданное число на две части по 8 бит каждый. Для каждой части мы можем искать в массиве count, сформированном на первом этапе. Например, если есть 16-разрядное число, например,
x = 1100110001011100, здесь число заданных бит = количество заданных бит в первом байте + количество заданных бит во втором байте. Поэтому для получения первого байта
y = (x & 0xff)
z = (x >> 8) & (0xff)
total set bits = count[y] + count[z]
Этот метод будет работать и в O (n).
Не уверен, если его поздно ответить, но вот мои выводы.
Пробовал решить проблему с помощью следующего подхода, для числа N каждый битно (от LSB до MSB, скажем, LSB начинается с битно 1 и увеличивается с последующим значением бита), количество битов может быть вычислено как (N/(2 topower битно) * (2 топора битно-1) + {(N% (2 топора битно)) - [(2 топора битно-1) - 1]}
Имейте письменную рекурсивную функцию для этого C/С++, пожалуйста, проверьте. Я не уверен, но я думаю, что его сложность - log (N). Параметр Pass function 2, номер (нет), для которого мы хотим, чтобы биты были вычислены, и второй стартовый счет из LSB, значение 1.
int recursiveBitsCal(int no, int bitno){
int res = int(no/pow(2,bitno))*int(pow(2,bitno-1));
int rem1 = int(pow(2,bitno-1)) -1;
int rem = no % int(pow(2,bitno));
if (rem1 < rem) res += rem -rem1;
if ( res <= 0 )
return 0;
else
return res + recursiveBitsCal(no, bitno+1);
}
for i in range(int(input())):
n=int(input())
c=0
m=13
if n==0:
print(c)
while n%8!=0 or n!=0:
t=bin(n)[2:]
c+=t.count('1')
n=n-1
if n!=0:
j=n//8
if j==1:
c+=m
else:
c+=m+((j-1)*7)
print(c)
int countSetBits(int n)
{
n++;
int powerOf2 = 2;
int setBitsCount = n/2;
while (powerOf2 <= n)
{
int numbersOfPairsOfZerosAndOnes = n/powerOf2;
setBitsCount += (numbersOfPairsOfZerosAndOnes/2) * powerOf2;
setBitsCount += (numbersOfPairsOfZerosAndOnes&1) ? (n%powerOf2) : 0;
powerOf2 <<= 1;
}
return setBitsCount;
}
Пожалуйста, проверьте мою статью на geeksforgeeks.org для подробного объяснения. Ниже ссылка на статьюhttps://www.geeksforgeeks.org/count-total-set-bits-in-all-numbers-from-1-to-n-set-2/
Я знаю, что это сообщение пришло поздно на вечеринку, пожалуйста, найдите решение logn ниже:
static int countSetBitWithinRange(int n)
{
int x = n + 1, index = 0, count = 0;
int numberOfOnesInAGroup = (int)Math.pow(2, index);
while(x >= numberOfOnesInAGroup)
{
int countOfZeroOnePairs = (x / numberOfOnesInAGroup);
int numberOfPairsOfZerosAndOnes = countOfZeroOnePairs / 2;
int numberOfSetBits = numberOfPairsOfZerosAndOnes * numberOfOnesInAGroup;
//If countOfZeroOnePairs is even then the pairs are complete else there will be ones that do not have a corresponding zeros pair
int remainder = (countOfZeroOnePairs % 2 == 1) ? (x % numberOfOnesInAGroup) : 0;
count = count + numberOfSetBits + remainder;
numberOfOnesInAGroup = 1 << ++index;
}
return count;
}
x = int(input("Any number:\n"))
y = (bin(x))
print(y)
v = len(y) -2
print(v)