Set right-adjacent bits
Set right-adjacent bits is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Given a left-to-right ordered collection of e
bits, b
, where 1 <= e <= 10000
,
and a zero or more integer n
:
- Output the result of setting the
n
bits to the right of any set bit inb
(if those bits are present in b and therefore also preserving the width, e
).
Some examples:
Set of examples showing how one bit in a nibble gets changed: n = 2; Width e = 4: Input b: 1000 Result: 1110 Input b: 0100 Result: 0111 Input b: 0010 Result: 0011 Input b: 0000 Result: 0000 Set of examples with the same input with set bits of varying distance apart: n = 0; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 010000000000100000000010000000010000000100000010000010000100010010 n = 1; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011000000000110000000011000000011000000110000011000011000110011011 n = 2; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011100000000111000000011100000011100000111000011100011100111011111 n = 3; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011110000000111100000011110000011110000111100011110011110111111111
Task:
- Implement a routine to perform the setting of right-adjacent bits on representations of bits that will scale over the given range of input width
e
. - Use it to show, here, the results for the input examples above.
- Print the output aligned in a way that allows easy checking by eyeof the binary input vs output.
Python
Python: Using arbitrary precision ints.
The set_right_adjacent_bits
function does all the real work.
<lang python>from operator import or_ from functools import reduce
def set_right_adjacent_bits(n: int, b: int) -> int:
return reduce(or_, (b >> x for x in range(n+1)), 0)
if __name__ == "__main__":
print("SAME n & Width.\n") n = 2 # bits to the right of set bits, to also set bits = "1000 0100 0010 0000" first = True for b_str in bits.split(): b = int(b_str, 2) e = len(b_str) if first: first = False print(f"n = {n}; Width e = {e}:\n") result = set_right_adjacent_bits(n, b) print(f" Input b: {b:0{e}b}") print(f" Result: {result:0{e}b}\n") print("SAME Input & Width.\n") #bits = "01000010001001010110" bits = '01' + '1'.join('0'*x for x in range(10, 0, -1)) for n in range(4): first = True for b_str in bits.split(): b = int(b_str, 2) e = len(b_str) if first: first = False print(f"n = {n}; Width e = {e}:\n") result = set_right_adjacent_bits(n, b) print(f" Input b: {b:0{e}b}") print(f" Result: {result:0{e}b}\n")</lang>
- Output:
SAME n & Width. n = 2; Width e = 4: Input b: 1000 Result: 1110 Input b: 0100 Result: 0111 Input b: 0010 Result: 0011 Input b: 0000 Result: 0000 SAME Input & Width. n = 0; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 010000000000100000000010000000010000000100000010000010000100010010 n = 1; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011000000000110000000011000000011000000110000011000011000110011011 n = 2; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011100000000111000000011100000011100000111000011100011100111011111 n = 3; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011110000000111100000011110000011110000111100011110011110111111111
Python: Using a list of 0 or 1 ints.
The set_right_adjacent_bits_list
function does all the real work.
<lang python>from typing import List import re
def set_right_adjacent_bits_list(n: int, b: List[int]) -> List[int]:
# [0]*x is padding b on the left. # zip(*(list1, list2,..)) returns the n'th elements on list1, list2,... # int(any(...)) or's them. return [int(any(shifts)) for shifts in zip(*([0]*x + b for x in range(n+1)))]
def _list2bin(b: List[int]) -> str:
"List of 0/1 ints to bool string." return re.sub(r'[\', "\[\]]', , str(b))
def _to_list(bits: str) -> List[int]:
return [int(char != '0') for char in bits]
if __name__ == "__main__":
print("SAME n & Width.\n") n = 2 # bits to the right of set bits, to also set bits = "1000 0100 0010 0000" first = True for b_str in bits.split(): b = _to_list(b_str) e = len(b_str) if first: first = False print(f"n = {n}; Width e = {e}:\n") result = set_right_adjacent_bits_list(n, b) print(f" Input b: {_list2bin(b)}") print(f" Result: {_list2bin(result)}\n") print("SAME Input & Width.\n") #bits = "01000010001001010110" bits = '01' + '1'.join('0'*x for x in range(10, 0, -1)) for n in range(4): first = True for b_str in bits.split(): b = _to_list(b_str) e = len(b_str) if first: first = False print(f"n = {n}; Width e = {e}:\n") result = set_right_adjacent_bits_list(n, b) print(f" Input b: {_list2bin(b)}") print(f" Result: {_list2bin(result)}\n")</lang>
- Output:
SAME n & Width. n = 2; Width e = 4: Input b: 1000 Result: 1110 Input b: 0100 Result: 0111 Input b: 0010 Result: 0011 Input b: 0000 Result: 0000 SAME Input & Width. n = 0; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 010000000000100000000010000000010000000100000010000010000100010010 n = 1; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011000000000110000000011000000011000000110000011000011000110011011 n = 2; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011100000000111000000011100000011100000111000011100011100111011111 n = 3; Width e = 66: Input b: 010000000000100000000010000000010000000100000010000010000100010010 Result: 011110000000111100000011110000011110000111100011110011110111111111