Рубрики

Подсчитать общее количество бит во всех числах от 1 до n

Учитывая положительное целое число n, подсчитайте общее количество установленных бит в двоичном представлении всех чисел от 1 до n.

Примеры:

Input: n = 3
Output:  4

Input: n = 6
Output: 9

Input: n = 7
Output: 12

Input: n = 8
Output: 13

Источник: Amazon Интервью Вопрос

Способ 1 (простой)
Простое решение состоит в том, чтобы запустить цикл от 1 до n и суммировать количество установленных бит во всех числах от 1 до n.

C ++

// Простая программа для подсчета установленных бит
// во всех числах от 1 до n.
#include <stdio.h>

  
// Утилита для подсчета установленных бит
// в числе х

unsigned int countSetBitsUtil(unsigned int x);

  
// Возвращает количество установленных битов, присутствующих во всех
// числа от 1 до n

unsigned int countSetBits(unsigned int n)

{

    int bitCount = 0; // инициализировать результат

  

    for (int i = 1; i <= n; i++)

        bitCount += countSetBitsUtil(i);

  

    return bitCount;

}

  
// Утилита для подсчета установленных бит
// в числе х

unsigned int countSetBitsUtil(unsigned int x)

{

    if (x <= 0)

        return 0;

    return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int n = 4;

    printf("Total set bit count is %d", countSetBits(n));

    return 0;

}

Джава

// Простая программа для подсчета установленных бит
// во всех числах от 1 до n.

  

class GFG{

  

    // Возвращает количество установленных битов

    // во всех числах от 1 до n

    static int countSetBits( int n)

    {

        // инициализировать результат

        int bitCount = 0;

      

        for (int i = 1; i <= n; i++)

            bitCount += countSetBitsUtil(i);

      

        return bitCount;

    }

      

    // Утилита для подсчета установленных бит

    // в числе х

    static int countSetBitsUtil( int x)

    {

        if (x <= 0)

            return 0;

        return (x % 2 == 0 ? 0 : 1) + 

               countSetBitsUtil(x / 2);

    }

      

    // Драйвер программы

    public static void main(String[] args)

    {

        int n = 4;

        System.out.print("Total set bit count is ");

        System.out.print(countSetBits(n));

    }

}

  
// Этот код предоставлен
// Смита Динеш Семвал

python3

# Простая программа для подсчета установленных бит
# во всех числах от 1 до n.

  
# Возвращает количество установленных битов, присутствующих во всех
# числа от 1 до n

def countSetBits(n):

      

    # инициализировать результат

    bitCount = 0 

  

    for i in range(1, n + 1):

        bitCount += countSetBitsUtil(i)

  

    return bitCount

  

  
# Полезная функция для подсчета установленных бит
# в числе х

def countSetBitsUtil(x):

  

    if (x <= 0):

        return 0

    return (0 if int(x % 2) == 0 else 1) +  countSetBitsUtil(int(x / 2))

  

  
# Драйверная программа

if __name__=='__main__'

    n = 4

    print("Total set bit count is", countSetBits(n))

       
# Этот код предоставлен
# Смита Динеш Семвал

C #

// Простая программа на C # для подсчета установленных бит
// во всех числах от 1 до n.

using System;

  

class GFG

{

    // Возвращает количество установленных битов

    // во всех числах от 1 до n

    static int countSetBits( int n)

    {

        // инициализировать результат

        int bitCount = 0;

      

        for (int i = 1; i <= n; i++)

            bitCount += countSetBitsUtil(i);

      

        return bitCount;

    }

      

    // Утилита для подсчета установленных бит

    // в числе х

    static int countSetBitsUtil( int x)

    {

        if (x <= 0)

            return 0;

        return (x % 2 == 0 ? 0 : 1) + 

            countSetBitsUtil(x / 2);

    }

      

    // Драйвер программы

    public static void Main()

    {

        int n = 4;

        Console.Write("Total set bit count is ");

        Console.Write(countSetBits(n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php 
// Простая программа для подсчета установленных бит
// во всех числах от 1 до n.

  
// Возвращает количество установленных битов
// во всех числах от 1 до n

function countSetBits($n)

{

    $bitCount = 0; // инициализировать результат

  

    for ($i = 1; $i <= $n; $i++)

        $bitCount += countSetBitsUtil($i);

  

    return $bitCount;

}

  
// Полезная функция для подсчета
// устанавливаем биты в число х

function countSetBitsUtil($x)

{

    if ($x <= 0)

        return 0;

    return ($x % 2 == 0 ? 0 : 1) + 

            countSetBitsUtil($x / 2);

}

  
// Код драйвера

$n = 4;

echo "Total set bit count is "

               countSetBits($n);

  
// Этот код предоставлен ChitraNayal
?>


Выход:

Total set bit count is 5

Сложность времени: O (nLogn)

Способ 2 (простой и эффективный, чем способ 1)
Если мы наблюдаем биты с самой правой стороны на расстоянии i, то биты инвертируются после позиции 2 ^ i в вертикальной последовательности.
например n = 5;
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101

Соблюдайте самый правый бит (i = 0), биты переворачиваются после (2 ^ 0 = 1)
Соблюдайте 3-й крайний правый бит (i = 2), после которого биты переворачиваются (2 ^ 2 = 4)

Таким образом, мы можем считать биты по вертикали так, что в i-м справа большинство позиционных битов будет перевернуто после 2-й итерации;

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Функция, которая считает установленные биты от 0 до n

int countSetBits(int n)

{

    int i = 0;

  

    // и храним сумму установленных битов от 0 до n

    int ans = 0; 

  

    // в то время как n больше, чем равно 2 ^ i

    while ((1 << i) <= n) {

  

        // Этот k будет перевернут после

        // 2 ^ i итераций

        bool k = 0;

  

        // изменить итератор с 2 ^ i на 1

        int change = 1 << i;

  

        // Это будет цикл от 0 до n для

        // позиция каждого бита

        for (int j = 0; j <= n; j++) {

  

            ans += k;

  

            if (change == 1) {

                k = !k; // Когда change = 1 перевернуть бит

                change = 1 << i; // снова установить изменение на 2 ^ i

            }

            else {

                change--;

            }

        }

  

        // увеличиваем позицию

        i++;

    }

  

    return ans;

}

  
// Основная функция

int main()

{

    int n = 17;

    cout << countSetBits(n) << endl;

    return 0;

}

Джава

public class GFG {

      

    // Функция, которая считает установленные биты от 0 до n

    static int countSetBits(int n)

    {

        int i = 0;

  

        // и храним сумму установленных битов от 0 до n

        int ans = 0;

  

        // в то время как n больше, чем равно 2 ^ i

        while ((1 << i) <= n) {

  

            // Этот k будет перевернут после

            // 2 ^ i итераций

            boolean k = false;

  

            // изменить итератор с 2 ^ i на 1

            int change = 1 << i;

  

            // Это будет цикл от 0 до n для

            // позиция каждого бита

            for (int j = 0; j <= n; j++) {

  

                if (k == true)

                    ans += 1;

                else

                    ans += 0;

  

                if (change == 1) {

                      

                    // Когда change = 1 перевернуть бит

                    k = !k; 

                      

                    // снова установить изменение на 2 ^ i

                    change = 1 << i; 

                }

                else {

                    change--;

                }

            }

  

            // увеличиваем позицию

            i++;

        }

  

        return ans;

    }

  

    // Драйвер программы

    public static void main(String[] args)

    {

        int n = 17;

          

        System.out.println(countSetBits(n));

    }

}

  
// Этот код предоставлен Sam007.

python3

# Функция, которая считает установленные биты от 0 до n

def countSetBits(n) :

    i = 0

  

    # и хранить сумму установленных битов от 0 до n

    ans = 0

  

    # в то время как n больше, чем равно 2 ^ i

    while ((1 << i) <= n) :

  

        # Этот k будет перевернут после

        # 2 ^ я итерации

        k = 0

  

        # изменение итератора с 2 ^ i на 1

        change = 1 << i

  

        # Это будет цикл от 0 до n для

        # позиция каждого бита

        for j in range(0, n+1) :

            ans += k

  

            if change == 1 :

                  

                # При изменении = 1 перевернуть бит

                k = not k

  

                # снова установите изменение на 2 ^ i

                change = 1 << i

  

            else :

                change -= 1

  

        # увеличить позицию

        i += 1

  

    return ans

  

  

  
# Код драйвера

if __name__ == "__main__" :

  

    n = 17

    print(countSetBits(n))

   
# Этот код предоставлен ANKITRAI1

C #

using System;

  

class GFG

{

    static int countSetBits(int n)

    {

        int i = 0;

  

        // и храним сумму установленных битов от 0 до n

        int ans = 0;

  

        // в то время как n больше, чем равно 2 ^ i

        while ((1 << i) <= n) {

  

            // Этот k будет перевернут после

            // 2 ^ i итераций

            bool k = false;

  

            // изменить итератор с 2 ^ i на 1

            int change = 1 << i;

  

            // Это будет цикл от 0 до n для

            // позиция каждого бита

            for (int j = 0; j <= n; j++) {

  

                if (k == true)

                    ans += 1;

                else

                    ans += 0;

  

                if (change == 1) {

                      

                    // Когда change = 1 перевернуть бит

                    k = !k; 

                      

                    // снова установить изменение на 2 ^ i

                    change = 1 << i; 

                }

                else {

                    change--;

                }

            }

  

            // увеличиваем позицию

            i++;

        }

  

        return ans;

    }

  

    // Драйвер программы

    static void Main()

    {

        int n = 17;

        Console.Write(countSetBits(n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Функция, которая считает
// устанавливаем биты от 0 до n

function countSetBits($n)

{

    $i = 0;

  

    // и храним сумму набора

    // биты от 0 до n

    $ans = 0; 

  

    // пока n больше чем

    // равно 2 ^ i

    while ((1 << $i) <= $n)

    {

  

        // Этот k будет перевернут

        // после 2 ^ i итераций

        $k = 0;

  

        // изменение - итератор

        // от 2 ^ i до 1

        $change = 1 << $i;

  

        // Это будет цикл от 0 до n

        // для каждой позиции бита

        for ($j = 0; $j <= $n; $j++) 

        {

            $ans += $k;

  

            if ($change == 1) 

            {

                // Когда change = 1 flip

                // бит

                $k = !$k

                  

                // снова установить изменение на 2 ^ i

                $change = 1 << $i

            }

            else 

            {

                $change--;

            }

        }

  

        // увеличиваем позицию

        $i++;

    }

  

    return $ans;

}

  
// Код драйвера

$n = 17;

echo(countSetBits($n));

  
// Этот код предоставлен Smitha
?>


Выход:

35

Сложность времени: O (k * n)
где k = количество бит для представления числа n
к <= 64

Метод 3 (хитрый)
Если входной номер имеет вид 2 ^ b -1, например, 1, 3, 7, 15 … и т. Д., То число установленных битов составляет b * 2 ^ (b-1). Это связано с тем, что для всех чисел от 0 до (2 ^ b) -1, если вы дополняете и переворачиваете список, вы получаете один и тот же список (половина бит включена, половина выключена).

Если число не имеет всех установленных битов, то некоторая позиция m является позицией крайнего левого установленного бита. Количество установленных битов в этой позиции равно n — (1 << m) + 1. Остальные установленные биты разделены на две части:

1) Биты в позициях (m-1) до точки, где крайний левый бит становится равным 0, и
2) 2 ^ (m-1) числа ниже той точки, которая является закрытой формой выше.

Простой способ взглянуть на это — рассмотреть число 6:

0|0 0
0|0 1
0|1 0
0|1 1
-|--
1|0 0
1|0 1
1|1 0

Самый левый установленный бит находится в позиции 2 (позиции считаются начиная с 0). Если мы замаскируем это, то останется 2 («1 0» в правой части последней строки). Таким образом, число бит во 2-й позиции (нижний левый прямоугольник) равно 3 (то есть 2 + 1) , Установленные биты от 0-3 (верхний правый прямоугольник выше): 2 * 2 ^ (2-1) = 4. В нижнем правом прямоугольнике указаны оставшиеся биты, которые мы еще не посчитали, и номер набора биты для всех чисел до 2 (значение последней записи в правом нижнем поле), которые могут быть вычислены рекурсивно.

C ++

#include <bits/stdc++.h>

  
// AO (Logn) сложность программы для подсчета
// устанавливаем биты во всех числах от 1 до n

using namespace std; 

  
/ * Возвращает позицию крайнего левого установленного бита.
Самая правая позиция считается
как 0 * /

unsigned int getLeftmostBit(int n) 

    int m = 0; 

    while (n > 1) 

    

        n = n >> 1; 

        m++; 

    

    return m; 

  
/ * Учитывая позицию предыдущего слева
установить бит в n (или верхнюю границу
крайняя левая позиция) возвращает новый
позиция крайнего левого установленного бита в n * /

unsigned int getNextLeftmostBit(int n, int m) 

    unsigned int temp = 1 << m; 

    while (n < temp) { 

        temp = temp >> 1; 

        m--; 

    

    return m; 

  
// Основная рекурсивная функция, используемая countSetBits ()

unsigned int _countSetBits(unsigned int n, int m); 

  
// Возвращает количество установленных бит в
// все числа от 1 до n

unsigned int countSetBits(unsigned int n) 

    // Получить позицию крайнего левого набора

    // бит в п. Это будет использоваться как

    // верхняя граница для следующей установленной битовой функции

    int m = getLeftmostBit(n); 

  

    // Используем позицию

    return _countSetBits(n, m); 

  

unsigned int _countSetBits(unsigned int n, int m) 

    // Базовый случай: если n равно 0, установить бит

    // количество равно 0

    if (n == 0) 

        return 0; 

  

    / * получить позицию следующего крайнего левого установленного бита * /

    m = getNextLeftmostBit(n, m); 

  

    // Если n имеет вид 2 ^ x-1, т.е. если n

    // это как 1, 3, 7, 15, 31, .. и т. д.,

    // тогда мы закончили.

    // Поскольку позиции считаются стартовыми

    // из 0 добавляется 1 к m

    if (n == ((unsigned int)1 << (m + 1)) - 1) 

        return (unsigned int)(m + 1) * (1 << m); 

  

    // обновляем n для следующего рекурсивного вызова

    n = n - (1 << m); 

    return (n + 1) + countSetBits(n) + m * (1 << (m - 1)); 

  
// Код драйвера

int main() 

    int n = 17; 

    cout<<"Total set bit count is "<< countSetBits(n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// AO (Logn) сложность программы для подсчета
// устанавливаем биты во всех числах от 1 до n
#include <stdio.h>

  
/ * Возвращает позицию крайнего левого установленного бита.

   Самая правая позиция считается

   как 0 * /

unsigned int getLeftmostBit(int n)

{

    int m = 0;

    while (n > 1) {

        n = n >> 1;

        m++;

    }

    return m;

}

  
/ * Учитывая позицию предыдущего слева

   установить бит в n (или верхнюю границу

   крайняя левая позиция) возвращает новый

   позиция крайнего левого установленного бита в n * /

unsigned int getNextLeftmostBit(int n, int m)

{

    unsigned int temp = 1 << m;

    while (n < temp) {

        temp = temp >> 1;

        m--;

    }

    return m;

}

  
// Основная рекурсивная функция, используемая countSetBits ()

unsigned int _countSetBits(unsigned int n, int m);

  
// Возвращает количество установленных бит в
// все числа от 1 до n

unsigned int countSetBits(unsigned int n)

{

    // Получить позицию крайнего левого набора

    // бит в п. Это будет использоваться как

    // верхняя граница для следующей установленной битовой функции

    int m = getLeftmostBit(n);

  

    // Используем позицию

    return _countSetBits(n, m);

}

  

unsigned int _countSetBits(unsigned int n, int m)

{

    // Базовый случай: если n равно 0, установить бит

    // количество равно 0

    if (n == 0)

        return 0;

  

    / * получить позицию следующего крайнего левого установленного бита * /

    m = getNextLeftmostBit(n, m);

  

    // Если n имеет вид 2 ^ x-1, т.е. если n

    // это как 1, 3, 7, 15, 31, .. и т. д.,

    // тогда мы закончили.

    // Поскольку позиции считаются стартовыми

    // из 0 добавляется 1 к m

    if (n == ((unsigned int)1 << (m + 1)) - 1)

        return (unsigned int)(m + 1) * (1 << m);

  

    // обновляем n для следующего рекурсивного вызова

    n = n - (1 << m);

    return (n + 1) + countSetBits(n) + m * (1 << (m - 1));

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int n = 17;

    printf("Total set bit count is %d", countSetBits(n));

    return 0;

}

Джава

// Java AO (Logn) программа для подсчета сложности
// устанавливаем биты во всех числах от 1 до n

import java.io.*;

  

class GFG 

{

      
/ * Возвращает позицию крайнего левого установленного бита.
Самая правая позиция считается
как 0 * /

static int getLeftmostBit(int n) 

    int m = 0

    while (n > 1

    

        n = n >> 1

        m++; 

    

    return m; 

  
/ * Учитывая позицию предыдущего слева
установить бит в n (или верхнюю границу
крайняя левая позиция) возвращает новый
позиция крайнего левого установленного бита в n * /

static int getNextLeftmostBit(int n, int m) 

    int temp = 1 << m; 

    while (n < temp) 

    

        temp = temp >> 1

        m--; 

    

    return m; 

  
// Основная рекурсивная функция, используемая countSetBits ()
// Возвращает количество установленных бит в
// все числа от 1 до n

  

static int countSetBits(int n) 

    // Получить позицию крайнего левого набора

    // бит в п. Это будет использоваться как

    // верхняя граница для следующей установленной битовой функции

    int m = getLeftmostBit(n); 

  

    // Используем позицию

    return countSetBits(n, m); 

  

static int countSetBits( int n, int m) 

    // Базовый случай: если n равно 0, установить бит

    // количество равно 0

    if (n == 0

        return 0

  

    / * получить позицию следующего крайнего левого установленного бита * /

    m = getNextLeftmostBit(n, m); 

  

    // Если n имеет вид 2 ^ x-1, т.е. если n

    // это как 1, 3, 7, 15, 31, .. и т. д.,

    // тогда мы закончили.

    // Поскольку позиции считаются стартовыми

    // из 0 добавляется 1 к m

    if (n == ((int)1 << (m + 1)) - 1

        return (int)(m + 1) * (1 << m); 

  

    // обновляем n для следующего рекурсивного вызова

    n = n - (1 << m); 

    return (n + 1) + countSetBits(n) + m * (1 << (m - 1)); 

  
// Код драйвера

public static void main (String[] args)

{

  

    int n = 17

    System.out.println ("Total set bit count is " + countSetBits(n)); 


}

  
// Этот код предоставлен ajit ..

python3

# AO (Logn) программа сложности для подсчета
# установить биты во всех числах от 1 до n

  
«»»
/ * Возвращает позицию крайнего левого установленного бита.
Самая правая позиция считается
как 0 * /
«»»

def getLeftmostBit(n):

  

    m = 0

    while (n > 1) :

  

        n = n >> 1

        m += 1

  

    return m

  
«»»
/ * Учитывая позицию предыдущего слева
установить бит в n (или верхнюю границу
крайняя левая позиция) возвращает новый
позиция крайнего левого установленного бита в n * /
«»»

def getNextLeftmostBit(n, m) :

  

    temp = 1 << m

    while (n < temp) :

        temp = temp >> 1

        m -= 1

  

    return m

  
# Основная рекурсивная функция, используемая countSetBits ()
# def _countSetBits (n, m)

  
# Возвращает количество установленных бит в
# все числа от 1 до n

def countSetBits(n) :

  

    # Получить позицию крайнего левого набора

    # бит в п. Это будет использоваться как

    # верхняя граница для следующей установленной функции бита

    m = getLeftmostBit(n)

  

    # Используйте позицию

    return _countSetBits(n, m)

  

def _countSetBits(n, m) :

  

    # Базовый случай: если n равно 0, установить бит

    # количество равно 0

    if (n == 0) :

        return 0

  

    # / * получить позицию следующего крайнего левого установленного бита * /

    m = getNextLeftmostBit(n, m)

  

    # Если n имеет вид 2 ^ x-1, т. Е. Если n

    # как 1, 3, 7, 15, 31, .. и т. д.,

    # тогда мы закончили.

    # Так как позиции считаются стартовыми

    # от 0, 1 добавляется к м

    if (n == (1 << (m + 1)) - 1) :

        return ((m + 1) * (1 << m))

  

    # обновить n для следующего рекурсивного вызова

    n = n - (1 << m)

    return (n + 1) + countSetBits(n) + m * (1 << (m - 1))

  
# Код драйвера

n = 17

print("Total set bit count is", countSetBits(n))

  
# Этот код предоставлен rathbhupendra

C #

// C # AO (Logn) программа для подсчета сложности
// устанавливаем биты во всех числах от 1 до n

using System;

  

class GFG

{

      
/ * Возвращает позицию крайнего левого установленного бита.
Самая правая позиция считается
как 0 * /

static int getLeftmostBit(int n) 

    int m = 0; 

    while (n > 1) 

    

        n = n >> 1; 

        m++; 

    

    return m; 

  
/ * Учитывая позицию предыдущего слева
установить бит в n (или верхнюю границу
крайняя левая позиция) возвращает новый
позиция крайнего левого установленного бита в n * /

static int getNextLeftmostBit(int n, int m) 

    int temp = 1 << m; 

    while (n < temp) 

    

        temp = temp >> 1; 

        m--; 

    

    return m; 

  
// Основная рекурсивная функция, используемая countSetBits ()
// Возвращает количество установленных бит в
// все числа от 1 до n

static int countSetBits(int n) 

    // Получить позицию крайнего левого набора

    // бит в п. Это будет использоваться как

    // верхняя граница для следующей установленной битовой функции

    int m = getLeftmostBit(n); 

  

    // Используем позицию

    return countSetBits(n, m); 

  

static int countSetBits( int n, int m) 

    // Базовый случай: если n равно 0,

    // затем устанавливаем количество битов 0

    if (n == 0) 

        return 0; 

  

    / * получить позицию следующего крайнего левого установленного бита * /

    m = getNextLeftmostBit(n, m); 

  

    // Если n имеет вид 2 ^ x-1, т.е. если n

    // это как 1, 3, 7, 15, 31, .. и т. д.,

    // тогда мы закончили.

    // Поскольку позиции считаются стартовыми

    // из 0 добавляется 1 к m

    if (n == ((int)1 << (m + 1)) - 1) 

        return (int)(m + 1) * (1 << m); 

  

    // обновляем n для следующего рекурсивного вызова

    n = n - (1 << m); 

    return (n + 1) + countSetBits(n) + 

                  m * (1 << (m - 1)); 

  
// Код драйвера

static public void Main ()

{

    int n = 17; 

    Console.Write("Total set bit count is " +

                            countSetBits(n)); 


}

  
// Этот код предоставлен Tushil.


Выход:

Total set bit count is 35

Сложность времени: O (Logn). С первого взгляда на реализацию сложность времени выглядит больше. Но если мы посмотрим поближе, операторы внутри цикла while цикла getNextLeftmostBit () выполняются для всех 0 битов в n. И количество выполненных рекурсий меньше или равно установленным битам в n. Другими словами, если элемент управления входит внутрь в то время как цикл getNextLeftmostBit (), тогда он пропускает те много битов в рекурсии.

Спасибо Агацу и IC за предложение этого решения.

Вот еще одно решение, предложенное Пиюшем Капуром .

Простое решение, использующее тот факт, что для i-го младшего разряда ответ будет

(N/2^i)*2^(i-1)+ X

где

X = N%(2^i)-(2^(i-1)-1)

тогда и только тогда

N%(2^i)>=(2^(i-1)-1)

int getSetBitsFromOneToN(int N){

    int two = 2,ans = 0;

    int n = N;

    while(n){

        ans += (N/two)*(two>>1);

        if((N&(two-1)) > (two>>1)-1) ans += (N&(two-1)) - (two>>1)+1;

        two <<= 1;

        n >>= 1;

    }

    return ans;

}

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитать общее количество бит во всех числах от 1 до n

0.00 (0%) 0 votes