Эффективный алгоритм для вычисления суммы количества цифр base2 (количества битов) в интервале положительных целых чисел

Попробуйте этот код, я думаю, он дает вам то, что вам нужно для вычисления двоичных файлов:

int bit(int x)
{
  if(!x) return 1;
  else
  {
    int i;
    for(i = 0; x; i++, x >>= 1);
    return i;
  }
}

Здесь главное понимать, что количество цифр, используемых для представления числа в двоичном формате, увеличивается на единицу с каждой степенью двойки:

+--------------+---------------+
| number range | binary digits |
+==============+===============+
|    0 - 1     |       1       |
+--------------+---------------+
|    2 - 3     |       2       |
+--------------+---------------+
|    4 - 7     |       3       |
+--------------+---------------+
|    8 - 15    |       4       |
+--------------+---------------+
|   16 - 31    |       5       |
+--------------+---------------+
|   32 - 63    |       6       |
+--------------+---------------+
|     ...      |      ...      |

Тогда тривиальным улучшением вашего алгоритма грубой силы было бы вычисление, во сколько раз это количество цифр увеличилось между двумя переданными числами (заданными логарифмом по основанию два), и сложение цифр путем умножения количества чисел, которые могут быть представлен заданным количеством цифр (заданным степенью двойки) с количеством цифр.

Наивная реализация этого алгоритма:

int digits_sum_seq(int a, int b)
{
    int sum = 0;
    int i = 0;
    int log2b = b <= 0 ? 1 : floor(log2(b));
    int log2a = a <= 0 ? 1 : floor(log2(a)) + 1;

    sum += (pow(2, log2a) - a) * (log2a);

    for (i = log2b; i > log2a; i--)
        sum += pow(2, i - 1) * i;

    sum += (b - pow(2, log2b) + 1) * (log2b + 1);

    return sum;
}

Затем его можно улучшить с помощью более эффективных версий функций log и pow, представленных в других ответах.

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

Ускоренный журнал 2 адаптирован из: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup

Метод таблицы поиска требует всего около 7 операций, чтобы найти журнал 32-битного значения. Если расширить до 64-битных величин, потребуется примерно 9 операций. Другая операция может быть сокращена с помощью четырех таблиц с возможными дополнениями, включенными в каждую. Использование элементов таблицы int может быть быстрее, в зависимости от вашей архитектуры.

Во-вторых, мы должны переосмыслить алгоритм. Если вы знаете, что числа между N и M имеют одинаковое количество цифр, сложите ли вы их одну за другой или лучше сделаете (M-N + 1) * numDigits?

Но если у нас есть диапазон, в котором встречается несколько чисел, что нам делать? Давайте просто найдем интервалы одинаковых цифр и сложим суммы этих интервалов. Реализовано ниже. Я думаю, что мой findEndLimit можно было бы дополнительно оптимизировать с помощью таблицы поиска.

Код

#include <stdio.h>
#include <limits.h>
#include <time.h>

unsigned int fastLog2(unsigned int v)
{
    static const char LogTable256[256] = 
    {
    #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
        -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
        LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
        LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
    };

    register unsigned int t, tt; // temporaries

    if (tt = v >> 16)
    {
      return (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
    }
    else 
    {
      return (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
    }
}

unsigned int numberOfBits(unsigned int i)
{
    if (i == 0) {
        return 1;
    }
    else {
        return fastLog2(i) + 1;
    }
}

unsigned int findEndLimit(unsigned int sx, unsigned int ex)
{
    unsigned int sy = numberOfBits(sx);
    unsigned int ey = numberOfBits(ex);
    unsigned int mx;
    unsigned int my;

    if (sy == ey) // this also means sx == ex
        return ex;

    // assumes sy < ey
    mx = (ex - sx) / 2 + sx; // will eq. sx for sx + 1 == ex
    my = numberOfBits(mx);
    while (ex - sx != 1) {
        mx = (ex - sx) / 2 + sx; // will eq. sx for sx + 1 == ex
        my = numberOfBits(mx);
        if (my == ey) {
            ex = mx;
            ey = numberOfBits(ex);
        }
        else {
            sx = mx;
            sy = numberOfBits(sx);
        }
    }
    return sx+1;
}

int main(void)
{
    unsigned int a, b, m;
    unsigned long l;
    clock_t start, end;
    l = 0;
    a = 0;
    b = UINT_MAX;

    start = clock();
    unsigned int i;
    for (i = a; i < b; ++i) {
        l += numberOfBits(i);
    }
    if (i == b) {
        l += numberOfBits(i);
    }
    end = clock();

    printf("Naive\n");
    printf("Digits: %ld; Time: %fs\n",l, ((double)(end-start))/CLOCKS_PER_SEC);

    l=0;
    start = clock();
    do {
        m = findEndLimit(a, b);
        l += (b-m + 1) * (unsigned long)numberOfBits(b);
        b = m-1;
    } while (b > a);
    l += (b-a+1) * (unsigned long)numberOfBits(b);
    end = clock();

    printf("Binary search\n");
    printf("Digits: %ld; Time: %fs\n",l, ((double)(end-start))/CLOCKS_PER_SEC);
}

Вывод

От 0 до UINT_MAX

$ ./main 
Naive
Digits: 133143986178; Time: 25.722492s
Binary search
Digits: 133143986178; Time: 0.000025s

Мой findEndLimit может занять много времени в некоторых крайних случаях:

От UINT_MAX / 16 + 1 до UINT_MAX / 8

$ ./main 
Naive
Digits: 7784628224; Time: 1.651067s
Binary search
Digits: 7784628224; Time: 4.921520s

По идее, вам нужно разделить задачу на две подзадачи: 1) найти сумму цифр от 0 до M и от 0 до N, а затем вычесть.

2) найдите этаж (log2 (x)), потому что, например, для числа 77 числа 64,65, ... 77 все имеют 6 цифр, следующие 32 - 5 цифр, следующие 16 - 4 цифры и так далее, что составляет геометрическую прогрессию.

Таким образом:

 int digits(int a) {
   if (a == 0) return 1;   // should digits(0) be 0 or 1 ?
   int b=(int)floor(log2(a));   // use any all-integer calculation hack
   int sum = 1 + (b+1) * (a- (1<<b) +1);  // added 1, due to digits(0)==1
   while (--b)
     sum += (b + 1) << b;   // shortcut for (b + 1) * (1 << b);
   return sum;
 }
 int digits_range(int a, int b) {
      if (a <= 0 || b <= 0) return -1;   // formulas work for strictly positive numbers
      return digits(b)-digits(a-1);
 }

Поскольку эффективность зависит от доступных инструментов, можно использовать аналогичный подход:

#include <stdlib.h>
#include <stdio.h>
#include <math.h> 

unsigned long long pow2sum_min(unsigned long long n, long long unsigned m)
{
  if (m >= n)
  {
    return 1;
  }

  --n;

  return (2ULL << n) + pow2sum_min(n, m);
}

#define LN(x) (log2(x)/log2(M_E))

int main(int argc, char** argv)
{
  if (2 >= argc)
  {
    fprintf(stderr, "%s a b\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  long a = atol(argv[1]), b = atol(argv[2]);

  if (0L >= a || 0L >= b || b < a)
  {
    puts("Na ...!");
    exit(EXIT_FAILURE);
  }

  /* Expand intevall to cover full dimensions: */
  unsigned long long a_c = pow(2, floor(log2(a)));
  unsigned long long b_c = pow(2, floor(log2(b+1)) + 1);

  double log2_a_c = log2(a_c);
  double log2_b_c = log2(b_c);

  unsigned long p2s = pow2sum_min(log2_b_c, log2_a_c) - 1;

  /* Integral log2(x) between a_c and b_c: */
  double A = ((b_c * (LN(b_c) - 1)) 
            - (a_c * (LN(a_c) - 1)))/LN(2)
            + (b+1 - a);

  /* "Integer"-integral - integral of log2(x)'s inverse function (2**x) between log(a_c) and log(b_c): */
  double D = p2s - (b_c - a_c)/LN(2);

  /* Corrective from a_c/b_c to a/b : */
  double C = (log2_b_c - 1)*(b_c - (b+1)) + log2_a_c*(a - a_c);

  printf("Total used digits: %lld\n", (long long) ((A - D - C) +.5));
}

:-)

Главное здесь - количество и вид выполненных итераций.

Номер

log(floor(b_c)) - log(floor(a_c))

раз

делать один

n - 1 /* Integer decrement  */
2**n + s /* One bit-shift and one integer addition  */

для каждой итерации.

Вот подход, полностью основанный на поиске. Вам даже не нужен log2 :)

Алгоритм

Сначала мы предварительно вычисляем пределы интервала, в которых количество битов может измениться, и создаем таблицу поиска. Другими словами, мы создаем массив limits[2^n], где limits[i] дает нам наибольшее целое число, которое может быть представлено (i+1) битами. Тогда наш массив будет {1, 3, 7, ..., 2^n-1}.

Затем, когда мы хотим определить сумму битов для нашего диапазона, мы должны сначала сопоставить наши пределы диапазона a и b с наименьшим индексом, для которого выполняется a <= limits[i] и b <= limits[j], который затем сообщит нам, что нам нужно (i+1) битов для представления a, и (j+1) биты для представления b.

Если индексы совпадают, то результат будет просто (b-a+1)*(i+1), в противном случае мы должны отдельно получить количество битов от нашего значения до края такого же количества бит интервала и также сложить общее количество бит для каждого интервала между ними. В любом случае простая арифметика.

Код

#include <stdio.h>
#include <limits.h>
#include <time.h>

unsigned long bitsnumsum(unsigned int a, unsigned int b)
{
    // generate lookup table
    // limits[i] is the max. number we can represent with (i+1) bits
    static const unsigned int limits[32] =
    {
    #define LTN(n) n*2u-1, n*4u-1, n*8u-1, n*16u-1, n*32u-1, n*64u-1, n*128u-1, n*256u-1
        LTN(1),
        LTN(256),
        LTN(256*256),
        LTN(256*256*256)
    };

    // make it work for any order of arguments
    if (b < a) {
        unsigned int c = a;
        a = b;
        b = c;
    }

    // find interval of a
    unsigned int i = 0;
    while (a > limits[i]) {
            ++i;
    }
    // find interval of b
    unsigned int j = i;
    while (b > limits[j]) {
            ++j;
    }

    // add it all up
    unsigned long sum = 0;
    if (i == j) {
        // a and b in the same range
        // conveniently, this also deals with j == 0
        // so no danger to do [j-1] below
        return (i+1) * (unsigned long)(b - a + 1);
    }
    else {
        // add sum of digits in range [a, limits[i]]
        sum += (i+1) * (unsigned long)(limits[i] - a + 1);
        // add sum of digits in range [limits[j], b]
        sum += (j+1) * (unsigned long)(b - limits[j-1]);
        // add sum of digits in range [limits[i], limits[j]]
        for (++i; i<j; ++i) {
            sum += (i+1) * (unsigned long)(limits[i] - limits[i-1]);
        }
        return sum;
    }
}

int main(void)
{
    clock_t start, end;
    unsigned int a=0, b=UINT_MAX;

    start = clock();
    printf("Sum of binary digits for numbers in range "
    "[%u, %u]: %lu\n", a, b, bitsnumsum(a, b));
    end = clock();
    printf("Time: %fs\n", ((double)(end-start))/CLOCKS_PER_SEC);
}

Вывод

$ ./lookup 
Sum of binary digits for numbers in range [0, 4294967295]: 133143986178
Time: 0.000282s

Алгоритм

Основная идея - найти n2 = log2(x) с округлением в меньшую сторону. Это количество цифр в x. Пусть pow2 = 1 << n2. n2 * (pow2 - x + 1) - количество цифр в значениях [x...pow2]. Теперь найдите солнце цифр в степенях 2 от 1 до n2-1.

Код

Я уверен, что можно сделать различные упрощения.
Непроверенный код. Рассмотрю позже.

// Let us use unsigned for everything.

unsigned ulog2(unsigned value) {
  unsigned result = 0;
  if (0xFFFF0000u & value) {
    value >>= 16; result += 16;
  }
  if (0xFF00u & value) {
    value >>= 8; result += 8;
  }
  if (0xF0u & value) {
    value >>= 4; result += 4;
  }
  if (0xCu & value) {
    value >>= 2; result += 2;
  }
  if (0x2 & value) {
    value >>= 1; result += 1;
  }
  return result;
}

unsigned bit_count_helper(unsigned x) {
  if (x == 0) {
    return 1;
  }
  unsigned n2 = ulog2(x);
  unsigned pow2 = 1u << n;
  unsigned sum = n2 * (pow2 - x + 1u);  // value from pow2 to x
  while (n2 > 0) {
    // ... + 5*16 + 4*8 + 3*4 + 2*2 + 1*1
    pow2 /= 2;
    sum += n2 * pow2;
  }
  return sum;
}

unsigned bit_count(unsigned a, unsigned b) {
  assert(a < b);
  return bit_count_helper(b - 1) - bit_count_helper(a);
}

Для этой проблемы ваше решение является самым простым, называется наивным, когда вы ищете каждый элемент в последовательности или, в вашем случае, интервал для проверки чего-либо или выполнения операций.

Наивный алгоритм

Предполагая, что a и b - положительные целые числа с b больше, чем a, давайте назовем измерение / размер интервала [a, b], n = (ba).

Имея наше количество элементов n и используя некоторые обозначения алгоритмов (например, обозначение большого O, ссылка) , стоимость наихудшего случая составляет O(n*(numberOfBits_cost)).

Из этого мы видим, что мы можем ускорить наш алгоритм, используя более быстрый алгоритм для вычисления numberOfBits (), или нам нужно найти способ не смотреть на каждый элемент интервала, который стоит нам n операций. .

Интуиция

Теперь, посмотрев на возможный интервал [6,14], вы увидите, что для 6 и 7 нам нужно 3 цифры, при этом 4 необходимо для 8,9,10,11,12,13,14. Это приводит к вызову numberOfBits () для каждого числа, которое использует одинаковое количество цифр для представления, тогда как следующая операция умножения будет быстрее:

(number_in_subinterval)*digitsForThisInterval
((14-8)+1)*4 = 28
((7-6)+1)*3 = 6

Таким образом, мы сократили цикл на 9 элементах с 9 операциями до 2.

Таким образом, написание функции, использующей эту интуицию, даст нам более эффективный во времени, а не обязательно в памяти, алгоритм. Используя вашу функцию numberOfBits (), я создал это решение:

   int intuitionSol(int a, int b){
    int digitsForA = numberOfBits(a);
    int digitsForB = numberOfBits(b);
    
    if(digitsForA != digitsForB){
        //because a or b can be that isn't the first or last element of the
        // interval that a specific number of digit can rappresent there is a need
        // to execute some correction operation before on a and b
        int tmp = pow(2,digitsForA)  - a;
        int result = tmp*digitsForA; //will containt the final result that will be returned
        
        int i;
        for(i = digitsForA + 1; i < digitsForB; i++){
            int interval_elements = pow(2,i) - pow(2,i-1);
            result = result + ((interval_elements) * i);
            //printf("NumOfElem: %i for %i digits; sum:= %i\n", interval_elements, i, result);
        }
        
        int tmp1 = ((b + 1) - pow(2,digitsForB-1));
        result = result + tmp1*digitsForB;
        return result;
    }
    else {
        int elements = (b - a) + 1;
        return elements * digitsForA; // or digitsForB
    }
}

Давайте посмотрим на стоимость. Стоимость этого алгоритма - это стоимость выполнения операции коррекции для a и b плюс самая дорогая операция цикла for. Однако в моем решении я не перебираю все элементы, а только numberOfBits(b)-numberOfBits(a), который в худшем случае, когда [0, n] становится log (n) -1 это эквивалентно O (log n). Чтобы продолжить, мы перешли от линейной стоимости операций O (n) к логарифмической стоимости O (log n) в худшем случае. Посмотрите на эту диаграмму различия между ними.

Примечание

Когда я говорю об интервале или подинтервале, я имею в виду интервал элементов, которые используют одинаковое количество цифр для представления числа в двоичном формате. Ниже приведены некоторые результаты моих тестов с последним, которые показывают разницу:

Considered interval is [0,4]
YourSol: 9 in time: 0.000015s
IntuitionSol: 9 in time: 0.000007s

Considered interval is [0,0]
YourSol: 1 in time: 0.000005s
IntuitionSol: 1 in time: 0.000005s

Considered interval is [4,7]
YourSol: 12 in time: 0.000016s
IntuitionSol: 12 in time: 0.000005s

Considered interval is [2,123456]
YourSol: 1967697 in time: 0.005010s
IntuitionSol: 1967697 in time: 0.000015s