What's the optimal implementation of a sliding window over a number's bits?

Question

Given a number i.e (0xD5B8), what is the most efficient way in Python to subset across the bits over a sliding window using only native libraries?

A method might look like the following:

def window_bits(n,w, s):
    '''
    n: the number
    w: the window size
    s: step size
    '''
    # code

window_bits(0xD5B8, 4, 4)  # returns [[0b1101],[0b0101],[0b1011],[0b1000]]
window_bits(0xD5B8, 2, 2)  # returns [[0b11],[0b01],[0b01],[0b01],[0b10],[0b11],[0b10],[0b00]]

Some things to consider:

1. should strive to use minimal possible memory footprint
2. can only use inbuilt libraries
3. as fast as possible.
4. if len(bin(n)) % w != 0, then the last window should exist, with a size less than w

Some of the suggestions are like How to iterate over a list in chunks, which is convert the int using bin and iterate over as a slice. However, these questions do not prove the optimality. I would think that there are other possible bitwise operations that could be done that are more optimal than running over the bin as a slice (a generic data structure), either from a memory or speed perspective. This question is about the MOST optimal, not about what gets the job done, and it can be considered from memory, speed, or both. Ideally, an answer gives good reasons why their representation is the most optimal.

So, if it is provably the most optimal to convert to bin(x) and then just manage the bits as a slice, then that's the optimal methodology. But this is NOT about an easy way to move a window around bits. Every op and bit counts in this question.

Answer 1

The "naive" option would be to create a bits array - bin(n)[2:] - and then use the answers from How to iterate over a list in chunks.

But this is most likely not so efficient assuming we can use bit operations. Another option is to shift-and-mask the input according to the window and step size:

def window_bits(n, w, step_size):
    offset = n.bit_length() - w  # the initial shift to get the MSB window
    mask = 2**w-1  # To get the actual window we need
    while offset >= 0:
        print(f"{(n >> offset)&mask:x}")
        offset -= step_size  # advance the window

And running window_bits(0xD5B8, 4, 4) will indeed print each nibble on a separate line.

Answer 2

This is not the full answer yet, as I need to do more research, but wanted to add it to the question.

Here's a modification of Tomerikoo's answer that handles the ends better.

This is the "blue" section of the graph below.

def window_bits(n, w, s):
    offset = n.bit_length() - w  
    mask = 2**w-1  
    ret = []
    while offset >= 0:
        ret.append((n >> offset) & mask)
        offset -= s  # advance the window
    if offset < 0: # close the end
        mask = 2**(-offset)-1
        ret.append((n >> mask) & mask)
    return ret

This, along with the red chunker algo mentioned next, was benchmarked over pytest benchamrk.

The red is the chunker used over the following function:

def chunker(n, size, s=None):
    seq = bin(n)
    return (seq[pos:pos + size] for pos in range(0, len(seq), size))

These were parameterized the same, with the following:

numbers = [2**n for n in range(10)]
window_size = [4, 8, 12]
step_size = window_size

A couple things that stood out to me:

1. The chunker has much more of an even execution time whereas the window_bit function executes with a lot more variance.
2. The chunker is just faster in general.

I'm looking into why this might be the case, as it's not clear yet to me if there's something else at play here. I would think that the bit shifting ops would be faster, but maybe there's some optimizations with slicing that's happening that I'm not sure about.

edit: there was a mistake above, and the chunker was returning a generator not actually running things over (duh). Tests show similar results though even with the fix. Thanks @Tomerikoo for the callout.

It should be:

def chunker(n, size, s=None):
    seq = bin(n)
    return ([seq[pos:pos + size] for pos in range(0, len(seq), size)])

Update Posting test code below:

import pytest

def window_bits(n, w, s):
    offset = n.bit_length() - w  # the initial shift to get the MSB window.
    mask = 2**w-1  # To get the actual window we need
    ret = []
    while offset >= 0:
        ret.append(bin((n >> offset) & mask)[2:].zfill(w))
        offset -= s  # advance the window
    if offset < 0: # close the end
        mask = 2**(-offset)-1
        ret.append(bin((n >> mask) & mask)[2:])
    return ret

def chunker(n, size, s=None):
    seq = bin(n)
    return([seq[pos:pos + size] for pos in range(0, len(seq), size)])

ns = [2**n for n in range(10)]
ws = [4, 8, 12]

@pytest.mark.parametrize('n', ns)
@pytest.mark.parametrize('ws', ws)
@pytest.mark.window_bits
def test_window_bits(benchmark, n, ws):
    result = benchmark.pedantic(window_bits, args=(n,ws,ws))
    assert result is not None

@pytest.mark.parametrize('n', ns)
@pytest.mark.parametrize('ws', ws)
@pytest.mark.chunker
def test_chunker(benchmark, n, ws):
    result = benchmark.pedantic(chunker, args=(n,ws,ws))
    assert result is not None