Алгоритм для вычисления числа 1s для диапазона чисел в двоичном

Ответ 1

Я думаю, что ключ сначала понимает структуру значений K и как быстро он растет. В принципе, у вас есть:

K(1) = 0
K(X) = K(bitcount(X))+1 for X > 1

Таким образом, найдя наименьшие значения X для данного K, видим, что

K(1) = 0
K(2) = 1
K(3) = 2
K(7) = 3
K(127) = 4
K(170141183460469231731687303715884105727) = 5

Итак, для примера, такого как 48238 10^18 9, ответ тривиален 0. K = 0 только для 1 и K = 1 только для степеней 2, поэтому в интересующей нас области мы увидим только значения K 2, 3 или 4 и никогда не видят K >= 5

изменить

Итак, мы ищем алгоритм для подсчета количества значений с K = 2,3,4 в диапазоне значений LO..HI без итерации по всему диапазону. Итак, первый шаг - найти количество значений в диапазоне с битконтом (x) == я для я = 1..59 (так как мы заботимся только о значениях до 10 18 и 10 18 18 2). Поэтому разложите диапазон lo..hi на поддиапазоны, которые имеют мощность 2 размера и отличаются только их младшими n битами - диапазон формы x * (2 ^ n).. (x + 1) * (2 ^ п) -1. Мы можем легко разбить диапазон арбитража на такие поддиапазоны. Для каждого такого поддиапазона будут выбраны значения (n, i) с битами я + битcount (x). Поэтому мы просто добавляем все поддиапазоны вместе, чтобы получить вектор счетчиков для 1..59, который мы затем перебираем, добавляя вместе эти элементы с тем же значением K, чтобы получить наш ответ.

изменить (исправлено снова, чтобы быть совместимым с C89 и работать для lo = 1/k = 0)

Здесь программа C для выполнения того, что я ранее описал:

#include <stdio.h>
#include <string.h>
#include <assert.h>

int bitcount(long long x) {
    int rv = 0;
    while(x) { rv++; x &= x-1; }
    return rv; }

long long choose(long long m, long long n) {
    long long rv = 1;
    int i;
    for (i = 0; i < n; i++) {
        rv *= m-i;
        rv /= i+1; }
    return rv; }

void bitcounts_p2range(long long *counts, long long base, int l2range) {
    int i;
    assert((base & ((1LL << l2range) - 1)) == 0);
    counts += bitcount(base);
    for (i = 0; i <= l2range; i++)
        counts[i] += choose(l2range, i); }

void bitcounts_range(long long *counts, long long lo, long long hi) {
    int l2range = 0;
    while (lo + (1LL << l2range) - 1 <= hi) {
        if (lo & (1LL << l2range)) {
            bitcounts_p2range(counts, lo, l2range);
            lo += 1LL << l2range; }
        l2range++; }
    while (l2range >= 0) {
        if (lo + (1LL << l2range) - 1 <= hi) {
            bitcounts_p2range(counts, lo, l2range);
            lo += 1LL << l2range; }
        l2range--; }
    assert(lo == hi+1); }

int K(int x) {
    int rv = 0;
    while(x > 1) {
        x = bitcount(x);
        rv++; }
    return rv; }

int main() {
    long long counts[64];
    long long lo, hi, total;
    int i, k;
    while (scanf("%lld%lld%d", &lo, &hi, &k) == 3) {
        if (lo < 1 || lo > hi || k < 0) break;
        if (lo == 0 || hi == 0 || k == 0) break;
        total = 0;
        if (lo == 1) {
            lo++;
            if (k == 0) total++; }
        memset(counts, 0, sizeof(counts));
        bitcounts_range(counts, lo, hi);
        for (i = 1; i < 64; i++)
            if (K(i)+1 == k)
                total += counts[i];
        printf("%lld\n", total); }
    return 0; }

который отлично работает для значений до 2 ^ 63-1 (LONGLONG_MAX). Для 48238 1000000000000000000 3 он дает 513162479025364957, что, безусловно, кажется правдоподобным

изменить

дающий входы

48238 1000000000000000000 1
48238 1000000000000000000 2
48238 1000000000000000000 3
48238 1000000000000000000 4

дает выходы

44
87878254941659920
513162479025364957
398959266032926842

Это добавляет до 999999999999951763, что является правильным. Величина k = 1 правильна (в этом диапазоне от 2 до 16 до 2 59 существует 44 степени. Поэтому, хотя я не уверен, что другие 3 значения верны, они, безусловно, правдоподобны.

Ответ 2

Идея этого ответа может помочь вам разработать очень быстрое решение. Имея диапазоны 0..2 ^ N, сложность потенциального алгоритма будет в наихудшем случае O (N) (Предполагая, что сложность длинной арифметики равна O (1)). Если она запрограммирована правильно, она должна легко обрабатывать N = 1000000 в вопрос миллисекунд.

Предположим, что мы имеем следующие значения:

LO   =          0; (0000000000000000000000000000000)
HI   = 2147483647; (1111111111111111111111111111111)

Самый низкий возможный N1 в диапазоне LO..HI равен 0 Максимально возможный N1 в диапазоне LO..HI равен 31

Итак, вычисление части N2..NN выполняется только для одного из 32 значений (то есть 0..31). Это можно сделать просто, даже без компьютера. Теперь давайте вычислим количество N1 = X для диапазона значений LO..HI

Когда мы имеем X = 0, мы имеем счет (N1 = X) = 1, это следующее значение:

1   0000000000000000000000000000000

Когда мы имеем X = 1, мы имеем счет (N1 = X) = 31, это следующие значения:

01  1000000000000000000000000000000
02  0100000000000000000000000000000
03  0010000000000000000000000000000
    ...
30  0000000000000000000000000000010
31  0000000000000000000000000000001

Когда мы имеем X = 2, мы имеем следующий шаблон:

1100000000000000000000000000000

Сколько уникальных строк может быть сформировано с 29 - '0' и 2 - '1'?

Представьте, что самый правый "1" (# 1) циклически перемещается слева направо, мы получаем следующее изображение:

01  1100000000000000000000000000000
02  1010000000000000000000000000000
03  1001000000000000000000000000000
    ...
30  1000000000000000000000000000001 

Теперь у нас есть 30 уникальных строк при перемещении '1' (# 1) слева направо, теперь невозможно создайте уникальную строку, перемещая '1' (# 1) в любом направлении. Это означает, что мы должны переместить '1' (# 2) вправо, пусть также reset положение '1' (# 1) как можно оставшейся единственной оставшейся уникальности, получим:

01  0110000000000000000000000000000

теперь мы снова выполняем циклирование '1' (# 1)

02  0101000000000000000000000000000
03  0100100000000000000000000000000
    ...
29  0100000000000000000000000000001

Теперь у нас есть 29 уникальных строк, продолжая всю эту операцию 28 раз, мы получаем следующее выражение

count(N1=2) = 30 + 29 + 28 + ... + 1 = 465

Когда мы имеем X = 3, картина остается аналогичной, но мы двигаем '1' (# 1), '1' (# 2), '1' (# 3)

Перемещение "1" (# 1) создает 29 уникальных строк, когда мы начинаем движение "1" (# 2), получаем

29 + 28 +... + 1 = 435 уникальных строк, после чего нам осталось обработать '1' (# 3), поэтому мы имеем

29 + 28 + ... + 1 = 435
     28 + ... + 1 = 406
          ...
              + 1 = 1

435 + 406 + 378 + 351 + 325 + 300 + 276 +
253 + 231 + 210 + 190 + 171 + 153 + 136 +
120 + 105 + 091 + 078 + 066 + 055 + 045 +
036 + 028 + 021 + 015 + 010 + 006 + 003 + 001 = 4495

Попробуем решить общий случай, например, когда мы имеем N нулей и M. Общее количество перестановок для строки длины (N + M) равно (N + M)!

Количество дубликатов '0' в этой строке равно N! Количество '1' дубликатов в этой строке равно M!

получая при этом общее количество уникальных строк, состоящих из N нулей и М,

              (N + M)!          32!       263130836933693530167218012160000000
F(N, M) =  ============= => ========== = ====================================== = 4495
            (N!) * (M!)      3! * 29!      6 * 304888344611713860501504000000

Edit:

F(N, M) = Binomial(N + M, M)

Теперь рассмотрим пример реальной жизни:

LO   =   43797207; (0000010100111000100101011010111)
HI   = 1562866180; (1011101001001110111001000000100)

Итак, как мы применяем нашу уникальную формулу перестановок к этому примеру? Поскольку мы не знаем, как много '1' находится ниже LO и сколько '1' находится выше HI.

Итак, давайте посчитаем эти перестановки ниже LO и выше HI.

Давайте вспомним, как мы циклировали "1" (# 1), "1" (# 2),...

1111100000000000000000000000000 => 2080374784
1111010000000000000000000000000 => 2046820352
1111001000000000000000000000000 => 2030043136
1111000000000000000000000000001 => 2013265921

1110110000000000000000000000000 => 1979711488
1110101000000000000000000000000 => 1962934272
1110100100000000000000000000000 => 1954545664
1110100010000000000000000000001 => 1950351361

Как вы видите, этот циклический процесс плавно уменьшает десятичные значения. Поэтому нам нужно посчитать количество пока мы не достигнем значения HI. Но мы не должны считать эти значения одним, потому что наихудший случай может генерировать до 32!/(16! * 16!) = 601080390 циклов, которые мы будем ездить на велосипеде очень долго:) Таким образом, нам нужны циклические куски "1" сразу.

В нашем примере мы хотели бы подсчитать количество циклов преобразования

1111100000000000000000000000000 => 1011101000000000000000000000000
                                   1011101001001110111001000000100

Итак, сколько циклов вызывает преобразование

1111100000000000000000000000000 => 1011101000000000000000000000000

?

Давайте посмотрим, что преобразование:

1111100000000000000000000000000 => 1110110000000000000000000000000

равно следующему набору циклов:

01  1111100000000000000000000000000
02  1111010000000000000000000000000
...
27  1111000000000000000000000000001
28  1110110000000000000000000000000

Итак, нам нужно 28 циклов для преобразования

1111100000000000000000000000000 => 1110110000000000000000000000000

Сколько циклов нам нужно преобразовать

1111100000000000000000000000000 => 1101110000000000000000000000000

выполняет следующие ходы, которые нам нужны:

1110110000000000000000000000000 28 cycles
1110011000000000000000000000000 27 cycles
1110001100000000000000000000000 26 cycles
...
1110000000000000000000000000011  1 cycle

и 1 цикл для приема:

1101110000000000000000000000000  1 cycle

получая таким образом 28 + 27 +... + 1 + 1 = 406 + 1

но мы видели это значение раньше, и это был результат для количества уникальных перестановок, который был вычислено для 2 '1' и 27 '0'. Это означает, что количество циклов при перемещении

11100000000000000000000000000 => 01110000000000000000000000000

равно перемещению

_1100000000000000000000000000 => _0000000000000000000000000011 

плюс один дополнительный цикл

поэтому это означает, что если мы имеем M нулей и N единиц и хотим переместить кусок U '1' вправо, нам нужно будет выполните следующее количество циклов:

      (U - 1 + M)!
1 + =============== = f(U, M)
     M! * (U - 1)!

Edit:

f(U, M) = 1 + Binomial(U - 1 + M, M)

Теперь вернемся к нашему примеру:

    LO   =   43797207; (0000010100111000100101011010111)
    HI   = 1562866180; (1011101001001110111001000000100)

поэтому мы хотим подсчитать количество циклов, необходимое для выполнения следующих (предположим, что N1 = 6)

1111110000000000000000000000000 => 1011101001000000000000000000000
                                   1011101001001110111001000000100

это равно:

1011101001000000000000000000000    1011101001000000000000000000000
-------------------------------    -------------------------------
_111110000000000000000000000000 => _011111000000000000000000000000 f(5, 25) = 118756
_____11000000000000000000000000 => _____01100000000000000000000000 f(2, 24) = 301
_______100000000000000000000000 => _______010000000000000000000000 f(1, 23) = 24
________10000000000000000000000 => ________01000000000000000000000 f(1, 22) = 23

что привело к 119104 "потерянным" циклам, которые расположены выше HI

Что касается LO, то на самом деле нет никакой разницы в том, в каком направлении мы ездим на велосипеде поэтому для вычисления LO мы можем делать обратное циклирование:

0000010100111000100101011010111    0000010100111000100101011010111
-------------------------------    -------------------------------
0000000000000000000000000111___ => 0000000000000000000000001110___ f(3, 25) = 2926
00000000000000000000000011_____ => 00000000000000000000000110_____ f(2, 24) = 301

Таким образом, в результате 3227 "потерянных" циклов, которые расположены ниже LO, это означает, что

overall amount of lost cycles = 119104 + 3227 = 122331

overall amount of all possible cycles = F(6, 25) = 736281

N1 in range 43797207..1562866180 is equal to 736281 - 122331 = 613950

Я не буду предоставлять оставшуюся часть решения. Остальная часть не так сложна. Удачи!

Ответ 3

Я думаю, что это проблема в дискретной математике,
если LOW равен 0,
иначе мы можем вставить функцию для суммирования чисел ниже LOW,
из показанных чисел я понимаю, что самое длинное число будет состоять максимум из 60 двоичных цифр не более

alg(HIGH,k)

l=len(HIGH)
sum=0;

for(i=0;i<l;i++)
{
 count=(l choose i); 
 nwia=numbers_with_i_above(i,HIGH); 
 if canreach(i,k) sum+=(count-nwia);
}

все номера отображаются не указан дважды numbers_with_i_above тривиально связаться с числами до 60 len - длина двоичного представления

Ответ 4

Zobgib,

Ключом к этой проблеме является не понимание того, как быстро растет рост K-модели, но КАК она растет. Первый шаг в этом состоит в том, чтобы понять (как сказал ваш тренер), как подсчитываются двоичные числа, поскольку это определяет все, о чем определяется K. Двоичные числа следуют шаблону, который отличается при подсчете количества положительных бит. Его единственный прогрессивный повторяющийся образец. Я собираюсь продемонстрировать необычным образом...

Assume i is an integer value. Assume b is the number of positive bits in i
i = 1; 
b = 1; 

i = 2; 3;
b = 1; 2;

i = 4; 5; 6; 7;
b = 1; 2; 2; 3;

i = 8; 9; 10; 11; 12; 13; 14; 15;
b = 1; 2;  2;  3;  2;  3;  3;  4;

i = 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31;
b =  1;  2;  2;  3;  2;  3;  3;  4;  2;  3;  3;  4;  3;  4;  4;  5; 

I assure you, this pattern holds to infinity, but if needed you
should be able to find or construct a proof easily.

Если вы посмотрите на приведенные выше данные, вы увидите отдельный шаблон, связанный с 2 ​​^ n. Каждый раз, когда у вас есть целочисленный показатель 2, шаблон будет reset, включая каждый член предыдущего шаблона, а затем каждый член предыдущего шаблона увеличивается на 1. Таким образом, чтобы получить K, вы просто применяете новый номер к рисунку выше. Ключ должен найти одно выражение (эффективное) для получения вашего количества бит.

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

Assume i is an integer value. Assume b is the number of positive bits in i
i = 1; 
b = 1; 
K = 1;

i = 2; 3;
b = 1; 2;
K = 1; 2;

i = 4; 5; 6; 7;
b = 1; 2; 2; 3;
K = 1; 2; 2; 3;

i = 8; 9; 10; 11; 12; 13; 14; 15;
b = 1; 2;  2;  3;  2;  3;  3;  4;
K = 1; 2;  2;  3;  2;  3;  3;  2;

i = 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31;
b =  1;  2;  2;  3;  2;  3;  3;  4;  2;  3;  3;  4;  3;  4;  4;  5; 
K =  1;  2;  2;  3;  2;  3;  3;  2;  2;  3;  3;  2;  3;  2;  2;  3;

Если вы заметили, что K следует аналогичному шаблону со специальным условием... Каждый раз, когда b является степенью 2, он фактически снижает значение K на 2. Soooo, если вы следуете бинарной прогрессии, вы должны быть способны чтобы легко отобразить ваши значения K. Поскольку эта модель зависит от степеней 2, а шаблон зависит от нахождения ближайшей мощности 2 и начала там, я предлагаю следующее решение. Возьмите значение LOW и найдите ближайшую мощность 2 (p), чтобы 2^p < LOW. Это можно сделать путем "подсчета бит" для самого низкого числа. Опять же, как только вы знаете, какой показатель он есть, вам не нужно подсчитывать бит для любого другого номера. Вы просто увеличиваете шаблон, и у вас будет свой b и, следовательно, K (который следует за одним и тем же шаблоном).

Примечание. Если вы особенно наблюдательны, вы можете использовать предыдущие b или K для определения следующего. Если текущий i нечетный, добавьте 1 к предыдущему b. Если текущий i делится на 4, вы уменьшаете b на 1 или 2, в зависимости от того, находится ли он в первой половине шаблона или второй половины. И, конечно, если i - степень 2, начните с 1.

Fuzzical Logic

Пример псевдокода (не оптимизированный)

{   var LOW, HIGH
    var power = 0

//Get Nearest Power Of 2 for (var i = 0 to 60) { // Compare using bitwise AND if (LOW bitAND (2 ^ i) = (2 ^ i)) { if ((2 ^ i) <= LOW) { set power to i } else { // Found the Power: end the for loop set i to 61 } } }

// Automatically 1 at a Power of 2 set numOfBits to 1 array numbersWithPositiveBits with 64 integers = 0 // Must create the pattern from Power of 2 set foundLOW to false for (var j = (2^power) to HIGH) { set lenOfPatten to (power + 1) // Don't record until we have found the LOW value if ((foundLOW is false) bitAND (j is equal to LOW)) { set foundLOW to true } // If j is odd, increment numOfBits if ((1 bitAND j) is equal to 1) { increment numOfBits } else if (j modulus 4 == 0) { decrement numOfBits accordingly //Figure this one out yourself, please } else if ((j - (2^power)) == (power + 1)) { // We are at the next power increment power // Start pattern over set numOfBits to 1 } // Record if appropriate if (foundLOW is equal to true) { increment element numOfBits in array numbersWithPositiveBits } }

// From here, derive your K values.

Ответ 5

Вы можете эффективно решить эту проблему следующим образом:

ret = 0;
for (i = 1; i <= 64; i++) {
  if (computeK(i) != desiredK) continue;
  ret += numBelow(HIGH, i) - numBelow(LO - 1, i);
}
return ret;

Функция numBelow(high, numSet) вычисляет количество целых чисел, меньших или равных high, и больше нуля, для которых установлены биты numSet. Чтобы эффективно реализовать numBelow(high, numSet), вы можете использовать что-то вроде следующего:

numBelow(high, numSet) {
  t = floor(lg(high));
  ret = 0;
  if (numBitsSet(high) == numSet) ret++;
  while (numSet > 0 && t > 0) {
    ret += nchoosek(t - 1, numSet);
    numSet--;
    while (--t > 0 && (((1 << t) & high) == 0));
  }
  return ret;
}