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

Question

Итак, я только что вернулся на соревнование по программированию ACM и справился довольно хорошо, но была одна проблема, которую не получила ни одна команда.

Проблема.

Начните с целого числа N0, которое больше 0. Пусть N1 будет числом единиц в двоичном представлении N0.Так что, если N0 = 27, N1 = 4.Для всех i > 0 пусть Ni будет числом единиц в двоичном представлении Ni-1.Эта последовательность всегда будет сходиться к одному.Для любого начального числа N0 пусть K будет минимальным значением i> = 0, для которого N1 = 1. Например, если N0 = 31, то N1 = 5, N2 = 2, N3 = 1, поэтому K = 3.

Учитывая диапазон последовательных чисел и значение X, сколько чисел в диапазоне имеют значение K, равное X?

Ввод
Там будетнесколько тестовых примеров на входе.Каждый тестовый случай будет состоять из трех целых чисел в одной строке: LO HI X
Где LO и HI (1 <= <code>LO <= <code>HI <= 10 ^ 18) - нижний и верхнийпределы диапазона целых чисел, и <code>X (0 <= <code>X <= 10) является целевым значением для K. Вход будет заканчиваться строкой из трех нулей. </p>

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

Пример ввода

31 31 3
31 31 1
27 31 1
27 31 2
1023 1025 1
1023 1025 2
0 0 0

Пример вывода

1
0
0
3
1
1

---

Если вы, ребята, хотите, я могу включитьнаш ответ или наша проблема, потому что поиск для небольшого диапазона очень прост, но я дам вам подсказку, чтобы ваша программа запускалась за секунд , а не минут.У нас было успешное решение, но не эффективный алгоритм для использования диапазона, подобного

48238 10^18 9

В любом случае, удачи, и если сообществу это нравится, у нас было еще немного, мы не могли бы решить, что может быть хорошим тизером для мозга.вы парни.Соревнование позволяет вам использовать Python, C ++ или Java - все три приемлемы в ответе.

---

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

Answer 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

edit

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

edit (снова исправлено, чтобы быть совместимым с 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, что, безусловно, кажется правдоподобным

edit

, давая входные данные

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

, дает выходные данные

44
87878254941659920
513162479025364957
398959266032926842

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

Answer 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) вправо, давайте также сбросим позицию '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 нулей и M, составляет

              (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

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

Answer 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 легко
длина бинарного представления

Answer 4

Зобгиб,

Ключ к этой проблеме не в том, чтобы понять, насколько быстро растет модель К, а в том, КАК она растет сама.Первым шагом в этом является понимание (как сказал ваш тренер), как учитываются двоичные числа, так как это определяет все, как определяется 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, шаблон будет сбрасываться путем включения каждого члена предыдущего шаблона, а затем каждый член предыдущего шаблона увеличивается на 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. Так что, если вы следуете бинарной последовательности, вы сможете легко отобразить ваши значения 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</p> <p>//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 } } }</p> <p>// 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 } }</p> <p>// From here, derive your K values.

Answer 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;
}