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 in b

(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 eye of 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