This may seem trivial but I haven't found a good solution to the problem. I have even found this: generate all n bit binary numbers in a fastest way possible. but I haven't found an exact duplicate.
The problem is very simple, given a limit N that is a positive integer, generate the binary representation of every natural number up to N in order (excluding N, the first natural number is 0, so N - 1 is the maximum number to be represented), in tuple form, with every tuple padded with leading zeros so that all representations are of the same length.
For example, if N is 4, the output should be [(0, 0), (0, 1), (1, 0), (1, 1)].
At this point this problem is indeed trivial, but there is a catch, no bin(n) and f'{n:b}' and the like are allowed, the algorithm should entirely operate in the binary domain, because as I understand everything (text, photos, music, videos...) in computers are binary numerals all the way down, so converting representations back and forth is adding unnecessary computations, these computations (base-conversion) are completely redundant and should be eliminated to produce the most efficient program (this is about keeping problems specific to as few domains as possible so that we only operate on those domains).
I wrote a simple program that does exactly what I describe:
from typing import Generator, Tuple
def count_in_binary(n: int) -> Generator[Tuple[int, ...], None, None]:
if not isinstance(n, int) or n < 1:
raise ValueError("The argument n must be a positive integer")
l = (n - 1).bit_length() if n > 1 else 1
numeral = [0] * l
maxi = l - 1
for _ in range(n):
yield tuple(numeral)
i = maxi
while True:
if not (d := numeral[i]):
numeral[i] = 1
break
else:
numeral[i] = 0
i -= 1
But I am not sure if this is the most efficient way to do it in Python. I haven't used many bit operations and computers already represent numbers as binary, so there should be faster ways to do this.
The question is, what is a faster way?
For comparison, here is one way that uses f'{n:b}' and therefore is more concise, but is actually much slower and stupider:
def count_in_binary1(n: int) -> Generator[Tuple[int, ...], None, None]:
if not isinstance(n, int) or n < 1:
raise ValueError("The argument n must be a positive integer")
l = len(f'{n-1:b}')
for i in range(n):
yield tuple(map(int, f'{i:0{l}b}'))
In [50]: %timeit list(count_in_binary(256))
59.9 μs ± 209 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
In [51]: %timeit list(count_in_binary1(256))
452 μs ± 3.68 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
I didn't do much testing with the original function, I just thought it would work, now it's fixed.
And no, the scope of the scope is limited to pure Python, so NumPy isn't allowed.
Now I think there are no exceptions.
I have upvoted and accepted the second answer as it does answer the original question though the original question doesn't include all the relevant information, so the problem I was trying to solve by posting a question remains unsolved.
I have posted a new question without all relevant information, please answer it: Fastest way to find all permutations of 0, 1 of width n without itertools in pure Python?
With itertools:
def count_in_binary(n: int) -> Iterator[Tuple[int, ...]]:
if not isinstance(n, int) or n < 1:
raise ValueError("The argument n must be a positive integer")
L = (n-1).bit_length() or 1
return islice(product((0, 1), repeat=L), n)
Benchmark results and code:
47 μs count_in_binary__original
15 μs count_in_binary__no_comment
345 μs count_in_binary__Sash_Sinha
from typing import Generator, Tuple, Iterator
from itertools import *
def count_in_binary__original(n: int) -> Generator[Tuple[int, ...], None, None]:
if not isinstance(n, int) or n < 1:
raise ValueError("The argument n must be a positive integer")
l = (n - 1).bit_length() if n > 1 else 1
numeral = [0] * l
maxi = l - 1
for _ in range(n):
yield tuple(numeral)
i = maxi
while True:
if not (d := numeral[i]):
numeral[i] = 1
break
else:
numeral[i] = 0
i -= 1
def count_in_binary__no_comment(n: int) -> Iterator[Tuple[int, ...]]:
if not isinstance(n, int) or n < 1:
raise ValueError("The argument n must be a positive integer")
L = (n-1).bit_length() or 1
return islice(product((0, 1), repeat=L), n)
def count_in_binary__Sash_Sinha(n: int) -> Generator[Tuple[int, ...], None, None]:
"""Yield binary tuples for 0 to n-1 with width = bit-length of n-1."""
if not isinstance(n, int) or n < 1:
raise ValueError('The argument n must be a positive integer.')
bit_length = (n - 1).bit_length() or 1
for i in range(n):
yield tuple((i >> j) & 1 for j in range(bit_length - 1, -1, -1))
funcs = [
count_in_binary__original,
count_in_binary__no_comment,
count_in_binary__Sash_Sinha,
]
for n in range(1, 100):
expect = list(count_in_binary__original(n))
for f in funcs:
result = list(f(n))
if result != expect:
print(n, f.__name__, result)
import timeit
for f in funcs:
t = min(timeit.repeat(lambda: list(f(256)), number=10**3)) * 1e3
print(f'{t:3.0f} μs ', f.__name__)