Формула для N-го количества битов (или количества населения) размера M

Тривиальное решение:

def count_same0(k: int) -> int:
    s = 0
    m = k.bit_count()
    for n in range(k):
        if n.bit_count() == m:
            s += n
    return s

Однако вместо этого вы можете попытаться сгенерировать все числа < k только с определенным количеством битов и посчитать их.

Вот простая попытка сделать это:

def count_same1(k: int) -> int:
    from itertools import permutations
    from math import log2, floor

    m = k.bit_count()
    positions = floor(log2(k)) + 1  # the total number of bit positions 

    s = 0
    # start generating unique permutations of positions #bits
    ps = set()
    for p in permutations([0] * (positions-m) + [1] * m):
        if p not in ps:
            ps.add(p)
            n = 0
            for b in p:
                n = (n << 1) | b
            # stop when we first exceed k
            if n >= k:
                break
            s += n

    return s 

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

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

def gen_int_n_ones(n: int) -> Generator[int, None, None]:
    from itertools import combinations

    z = 0
    while True:
        bits_cs = list(combinations(range(1, n), z))
        yield from (sum(0 if i in bits else 2**(n-(i+1)) for i in range(n)) for bits in bits_cs)
        z += 1
        n += 1


def count_same2(k: int) -> int:
    s = 0
    for n in gen_int_n_ones(k.bit_count()):
        if n >= k:
            break
        s += n

    return s

Однако наивное решение использует операции, которые настолько эффективны, что эффективнее просто проверить все числа, а не решать, каких из них следует избегать.

Попробуйте запустить это:

def main():
    from timeit import timeit

    for x in range(1, 100):
        print(x, count_same0(x), count_same1(x), count_same2(x))
        print(
            timeit(lambda: count_same0(x), number=10000), 
            timeit(lambda: count_same1(x), number=10000), 
            timeit(lambda: count_same2(x), number=10000)
        )

Вы обнаружите, что count_same0 — самый быстрый (на самом деле, просто быстрый) и что count_same2 лучше, чем count_same1, но не приближается к count_same0.

Поэтому я думаю, что простой ответ на самом деле:

def n_for_k(k: int) -> int:
    b = k.bit_count()
    return sum(1 for i in range(k) if i.bit_count() == b)

Однако для вашего примера значения 123456789123456789123456789 это займет много времени. Однако я сомневаюсь, что существует известное более простое решение, учитывая, что (после решения, как описано выше) я также нашел последовательность в OEIS: https://oeis.org/A079071 и она по сути определяет то же самое. (и глядя на график, лучше не становится: https://oeis.org/A079071/graph)

Кто или что поручил вам решить эту задачу?

Я не знаю Python, так что это Ruby. Алгоритм должен легко транслироваться. Идея состоит в том, чтобы для каждого установленного бита (от меньшего к большему) подсчитать все числа, которые одинаковы слева от этого бита, имеют одинаковое количество установленных битов в этом бите и справа от него, но не имеют одинакового количества установленных битов в этом бите и справа от него. этот бит установлен.

• Перемещайте биты вашего ввода от меньшего к большему.
• Следите за установленными просмотренными битами и общим количеством просмотренных битов.
• Подсчитайте все числа с одинаковым количеством видимых установленных битов, но с меньшим максимальным установленным битом (чем текущий индекс) каждый раз, когда вы встречаете установленный бит.
• Например, при достижении меньшего 1 из 10100 мы добавляем 2 к счету, потому что есть 2 числа с 1 установленным битом и меньшим максимальным установленным битом: 10 и 01.

Код:

def g(k)
  set_bits_seen = 0
  all_bits_seen = 0
  
  total = 0
  
  while k > 0
    all_bits_seen += 1
    
    if k % 2 == 1 # cur bit is set
      set_bits_seen += 1
      if all_bits_seen > set_bits_seen
        total += n_choose_k(all_bits_seen - 1, set_bits_seen)
      end
    end
    k /= 2
  end
  return total
end

def n_choose_k(n, k)
  return 1 if k == 0 or k == n
  (k + 1 .. n).reduce(:*) / (1 .. n - k).reduce(:*)
end

Полученные результаты:

1.upto(20) do |i|
  puts "#{i.to_s(2)}  --  #{g(i)}"
end

1  --  0
10  --  1
11  --  0
100  --  2
101  --  1
110  --  2
111  --  0
1000  --  3
1001  --  3
1010  --  4
1011  --  1
1100  --  5
1101  --  2
1110  --  3
1111  --  0
10000  --  4
10001  --  6
10010  --  7
10011  --  4
10100  --  8

И для вашего большого примера:

> g(123456789123456789123456789)
=> 3594960708495168399327022

Выражение числа в виде комбинации битов и вычисление индекса комбинации:

from more_itertools import combination_index
from math import comb

K = 123456789123456789123456789

M = K.bit_length()
c = [i for i, b in enumerate(f'{K:b}') if b == '1']
N = comb(M, len(c)) - 1 - combination_index(c, range(M))

print(N)

Вывод (тот же, что и у Дэйва):

3594960708495168399327022

Черт, я только что понял, что тебе нужна «простая формула». Ну что ж. Возможно, это все еще полезно для людей, которые приходят сюда в поисках простого кода.

Результат

Для вычислений в любом направлении (от битовой строки k до количества бит m и индекса n или от количества битов и индекса до битовой строки) требуется всего несколько арифметических операций на битовую позицию. Реализации Python и C приведены ниже.

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

static void BitStringToIndex(unsigned Bits, unsigned *NBits, unsigned *Index)
{
    unsigned b = 0;
    while (Bits>>b & 1)
        ++b;
    unsigned m = b, n = 0, c = 1;
    while (Bits>>++b)
        if (Bits>>b & 1)
            n += (c = c * b / ++m);
        else
            c = c * b / (b-m);
    *NBits = m;
    *Index = n;
}


static unsigned IndexToBitString(unsigned m, unsigned n)
{
    unsigned b = m, c = 1;
    for (unsigned t; (t = c * (b+1) / ((b+1)-m)) <= n; ++b)
        c = t;
    unsigned k = 0;
    for (; n; --b)
    {
        if (c <= n)
        {
            n -= c;
            k |= 1;
            c = c * m-- / b;
        }
        else
            c = c * (b-m) / b;
        k <<= 1;
    }
    k <<= b;
    k |= (1u << m) - 1;
    return k;
}

Алгоритмы

Число способов расположить m 1 бит в b позициях с 0 битами в остальных m−b позициях равно _bC_m = b! / м! / (б-м)!.¹

В этом ответе позиции битов нумеруются 0 для наименее значимого, затем 1 для следующего и так далее. Двоичное число 10000 имеет 1 в битовой позиции 4 и 4 нуля «справа» от него или «ниже».

Рассмотрим список двоичных чисел в порядке возрастания с фиксированным количеством 1 бит. Прежде чем бит в позиции b сможет стать 1 (если он не начинается с 1), либо с начала списка, либо с момента последнего изменения с 1 на 0, биты b справа от него должны пройти через все _bC _m расположение битов m 1 в битах b, где m — количество битов 1 в позиции b и ниже. Число с 1 битом в позициях b₀, b₁, b₂,…, каждое из которых соответствует соответствующему m₀, m₁, m₂,… , появляется после шагов _b0C_m0 в списке, чтобы получить 1 в бите b₀ плюс _b1 C_m1 выполняет шаги в списке, чтобы получить 1 в бите b₁, и так далее. Итак, все, что нам нужно сделать, чтобы найти позицию этого числа в списке, — это добавить _bC_m к каждому биту, кроме тех, что вместе справа.² Это показывает процедура BitStringToIndex ниже.

И наоборот, учитывая количество битов m и индекс n, мы находим наибольшее значение b до того, как _bC_m превысит n, и это говорит нам, где находится первый бит в битовой строке. Тогда строка, которую мы ищем, представляет собой n − _bC_m шагов в списке после того места, где впервые появляется этот ведущий 1 бит, поэтому мы можем обновить n, а затем определить позицию следующего 1 бита. Об этом свидетельствует рутина IndexToBitString.

В этом описании алгоритмов _bC_m неоднократно упоминается. Однако нам не нужно каждый раз рассчитывать его с нуля. По мере перехода от _bC_m к _b+1C_m или _b+1C_m+1 значение C изменяется на один множитель в числителе и на один множитель в знаменателе. Это показано в комментариях в коде ниже. Таким образом, одного умножения и одного деления на позицию бита достаточно для поддержания постоянного значения этой функции.

Реализация Python

# At several points, comments mention maintaining c = C(b, m).  This means
# that, as the values of b and/or m change, the value of c is modified so
# that it remains equal to C(b, m) for the new values of b or m.


# Convert bit string Bits (a binary numeral) to the number of 1 bits it
# contains and the index of that string in ascending lexicographic order of the
# strings with that number of 1 bits.
def BitStringToIndex(Bits):

    # Set b to the position number of the lowest 0 bit in Bits.
    b = 0
    while Bits>>b & 1:
        b += 1

    # Start with number of bits b and index 0.  Maintain c = C(b, m) =
    # b! / m! / (b-m)!, the number of ways to arrange m 1 bits and b-m 0 bits
    # in b positions.
    m = b
    n = 0
    c = 1

    # Increment b and continue while there are further 1 bits at or above b.
    b += 1
    while Bits>>b:

        # If bit b is 1, count another 1 bit (++m) and add to the index n
        # the number of arrangements we have passed -- all the arrangements
        # of m 1 bits in the b positions below position b, C(b, m).
        #
        # Update c to transition to the new C(b, m) from the prior
        # C(b-1, m-1): C(b, m) / C(b-1, m-1) =
        # b! / m! / (b-m)! / ((b-1)! / (m-1)! / ((b-1) - (m-1))!) = b / m.
        if Bits>>b & 1:
            m += 1
            c = c * b // m
            n += c

        # If bit is 0, do not update the index.  Merely update c:
        # C(b, m) / C(b-1, m) =
        # b! / m! / (b-m)! / ((b-1)! / m! / ((b-1)-m)!) = b / (b-m).
        else:
            c = c * b // (b-m)

        b += 1

    # Return the bit count and the index.
    return [m, n]


# Convert a number of 1 bits, m, and an index, n, of a bit string in ascending
# lexicographic order of the strings with that number of 1 bits to the bit
# string (a binary numeral).
def IndexToBitString(m, n):

    # Find highest bit and maintain c = C(b, m) = b! / m! / (b-m)!,
    # the number of ways to arrange m 1 bits and b-m 0 bits in b positions.
    b = m
    c = 1
    while 1:
        t = c * (b+1) // ((b+1)-m)
        if n < t:
            break
        c = t
        b += 1

    # Start the index k at zero.  For each bit position b, in descending
    # order, test whether the index n indicates we have passed C(b, m) prior
    # arrangements.  If so, there is a 1 at the current bit position, and we
    # decrement m by 1 to account for the 1 bit here and n by C(b, m) to
    # account for the number of prior arrangements.
    k = 0

    # Continue until base case, index n is zero, at which time there are m 1
    # bits in the m low positions.
    while 0 < n:
    
        # If n equals or exceeds C(b, m), we passed all prior arrangements
        # of m bits in the b lower positions, so there must be a 1 bit here.
        if c <= n:
            # Decrement n for the number of prior arrangements.
            # 
            # Put a 1 bit at this position.  (We shift k later.)
            # 
            # Update c to C(b-1, m-1) from C(b, m):  C(b-1, m-1) / C(b, m) =
            # (b-1)! / (m-1)! / ((b-1)-(m-1))! / (b! / m! / (b-m)!) =
            # m / b.
            # 
            # Decrement m by 1 for this 1 bit.
            n -= c
            k |= 1
            c = c * m // b
            m -= 1

        # Otherwise, merely update c to C(b-1, m) from C(b, m):
        # C(b-1, m) / C(b, m) =
        # (b-1)! / m! / ((b-1)-m)! / (b! / m! / (b-m)!) = (b-m) / b.
        else:
            c = c * (b-m) // b

        # Shift k to work on next bit position.
        k <<= 1;

        b -= 1

    # The loop above can be made sufficient to construct all of k by running
    # it down to a final iteration in which b is zero (which requires some
    # care in the loop limit and avoiding division by zero in updating c).
    # That is mathematically aesthetic, but, once n reaches zero, we can
    # handle the final bits directly with the code below.

    # The bit at position 0 in the value under construction in k is destined
    # to be bit b in the final value, so shift k.
    k <<= b

    # Here n is zero which is the index for all m 1 bits in the low
    # positions. Add this to k, and we are done.
    k |= (1 << m) - 1

    return k;


for k in range (32):
    m, n = BitStringToIndex(k)
    print(k, m, n)
    t = IndexToBitString(m, n)
    if t != k:
        print("Error, expected ({}, {}) -> {} but got {}.".format(m, n, t, k))
        exit(1)

C Реализация

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


/*  At several points, comments mention maintaining c = C(b, m).  This means
    that, as the values of b and/or m change, the value of c is modified so
    that it remains equal to C(b, m) for the new values of b or m.
*/


/*  Convert bit string Bits (a binary numeral) to the number of 1 bits it
    contains, *NBits, and the index, *Index, of that string in ascending
    lexicographic order of the strings with that number of 1 bits.
*/
static void BitStringToIndex(unsigned Bits, unsigned *NBits, unsigned *Index)
{
    //  Set b to the position number of the lowest 0 bit in Bits.
    unsigned b = 0;
    while (Bits>>b & 1)
        ++b;

    /*  Start with number of bits b and index 0.  Maintain c = C(b, m) =
        b! / m! / (b-m)!, the number of ways to arrange m 1 bits and b-m 0 bits
        in b positions.
    */
    unsigned m = b, n = 0, c = 1;

    //  Increment b and continue while there are further 1 bits at or above b.
    while (Bits>>++b)

        /*  If bit b is 1, count another 1 bit (++m) and add to the index n
            the number of arrangements we have passed -- all the arrangements
            of m 1 bits in the b positions below position b, C(b, m).

            Update c to transition to the new C(b, m) from the prior
            C(b-1, m-1): C(b, m) / C(b-1, m-1) =
            b! / m! / (b-m)! / ((b-1)! / (m-1)! / ((b-1) - (m-1))!) = b / m.
        */
        if (Bits>>b & 1)
            n += (c = c * b / ++m);

        /*  If bit is 0, do not update the index.  Merely update c:
            C(b, m) / C(b-1, m) =
            b! / m! / (b-m)! / ((b-1)! / m! / ((b-1)-m)!) = b / (b-m).
        */
        else
            c = c * b / (b-m);

    //  Return the bit count and the index.
    *NBits = m;
    *Index = n;
}


/*  Convert a number of 1 bits, m, and an index, n, of a bit string in
    ascending lexicographic order of the strings with that number of 1 bits to
    the bit string (a binary numeral).
*/
static unsigned IndexToBitString(unsigned m, unsigned n)
{
    /*  Find highest bit and maintain c = C(b, m) = b! / m! / (b-m)!,
        the number of ways to arrange m 1 bits and b-m 0 bits in b positions.

        The unusual loop construction is due to the fact we want to test
        whether increasing b would yield n < C(b, m), in which case we want to
        use b before increasing it.  So a temporary value t is assigned the
        value of what C(b, m) would be if b were increased.  If it does not
        exceed n, c is updated and b is increased, and the loop continues.
    */
    unsigned b = m, c = 1;
    for (unsigned t; (t = c * (b+1) / ((b+1)-m)) <= n; ++b)
        c = t;

    /*  Start the index k at zero.  For each bit position b, in descending
        order, test whether the index n indicates we have passed C(b, m) prior
        arrangements.  If so, there is a 1 at the current bit position, and we
        decrement m by 1 to account for the 1 bit here and n by C(b, m) to
        account for the number of prior arrangements.
    */
    unsigned k = 0;

    /*  Continue until base case, index n is zero, at which time there are m 1
        bits in the m low positions.
    */
    for (; n; --b)
    {
        /*  If n equals or exceeds C(b, m), we passed all prior arrangements
            of m bits in the b lower positions, so there must be a 1 bit here.
        */
        if (c <= n)
        {
            /*  Decrement n for the number of prior arrangements.

                Put a 1 bit at this position.  (We shift k later.)

                Update c to C(b-1, m-1) from C(b, m):  C(b-1, m-1) / C(b, m) =
                (b-1)! / (m-1)! / ((b-1)-(m-1))! / (b! / m! / (b-m)!) =
                m / b.

                Decrement m by 1 for this 1 bit.
            */
            n -= c;
            k |= 1;
            c = c * m-- / b;
        }

        /*  Otherwise, merely update c to C(b-1, m) from C(b, m):
            C(b-1, m) / C(b, m) =
            (b-1)! / m! / ((b-1)-m)! / (b! / m! / (b-m)!) = (b-m) / b.
        */
        else
            c = c * (b-m) / b;

        //  Shift k to work on next bit position.
        k <<= 1;
    }
    /*  The loop above can be made sufficient to construct all of k by running
        it down to a final iteration in which b is zero (which requires some
        care in the loop limit and avoiding division by zero in updating c).
        That is mathematically aesthetic, but, once n reaches zero, we can
        handle the final bits directly with the code below.
    */

    /*  The bit at position 0 in the value under construction in k is destined
        to be bit b in the final value, so shift k.
    */
    k <<= b;

    /*  Here n is zero which is the index for all m 1 bits in the low
        positions. Add this to k, and we are done.
    */
    k |= (1u << m) - 1;

    return k;
}


int main(void)
{
    for (unsigned k = 0; k < 32; ++k)
    {
        unsigned m, n;
        BitStringToIndex(k, &m, &n);
        printf("%u %u %u\n", k, m, n);
        unsigned t = IndexToBitString(m, n);
        if (t != k)
        {
            fprintf(stderr, "Error, expected (%u, %u) -> %u but got %u.\n",
                m, n, k, t);
            exit(EXIT_FAILURE);
        }
    }
}

Сноски

¹ Это известный элементарный результат комбинаторики. Иногда ее называют функцией «n выбирают k», потому что это также количество способов выбора k объектов из n и обычно пишется _nC_k. Фактически размещение m1 бит в b позициях означает выбор m позиций из b позиций. Однако, поскольку в вопросе n и k используются для других целей, я не смог использовать их для этого.

² Крайние правые биты изначально содержат 1, поэтому для установки их в 1 не требуется никаких шагов по списку, поэтому они не вносят вклад в индекс.