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

Raku

A left-to-right ordered collection of bits is more commonly referred to as an Integer in Raku.

<lang perl6>sub rab (Int $n is copy, Int $b = 1) {

   for 1..$n.msb -> $i {
       next unless $n +& (1 +< $i);
       $n +|= exp($i - $_, 2) for 1 .. $b
   }
   $n

}

sub lab (Int $n is copy, Int $b = 1) {

   for $n.msb … 0 -> $i {
       next unless $n +& (1 +< $i);
       $n +|= exp($i + $_, 2) for 1 .. $b
   }
   $n

}

1. Test with a few integers.

for 8,4, 18455760086304825618,5, 5444684034376312377319904082902529876242,15 -> $integer, $bits {

   say "\nInteger: $integer - Right-adjacent-bits: up to $bits";

   .say for ^$bits .map: -> $b { $integer.&rab($b).base: 2 };

   say "\nInteger: $integer - Left-adjacent-bits: up to $bits";

   .say for ^$bits .map: -> $b { $integer.&lab($b).fmt("%{0~$bits+$integer.msb}b") };

}</lang>

Output:

Integer: 8 - Right-adjacent-bits: up to 4
1000
1100
1110
1111

Integer: 8 - Left-adjacent-bits: up to 4
0001000
0011000
0111000
1111000

Integer: 18455760086304825618 - Right-adjacent-bits: up to 5
10000000000100000000010000000010000000100000010000010000100010010
11000000000110000000011000000011000000110000011000011000110011011
11100000000111000000011100000011100000111000011100011100111011111
11110000000111100000011110000011110000111100011110011110111111111
11111000000111110000011111000011111000111110011111011111111111111

Integer: 18455760086304825618 - Left-adjacent-bits: up to 5
000010000000000100000000010000000010000000100000010000010000100010010
000110000000001100000000110000000110000001100000110000110001100110110
001110000000011100000001110000001110000011100001110001110011101111110
011110000000111100000011110000011110000111100011110011110111111111110
111110000001111100000111110000111110001111100111110111111111111111110

Integer: 5444684034376312377319904082902529876242 - Right-adjacent-bits: up to 15
1000000000000001000000000000010000000000000100000000000010000000000010000000000100000000010000000010000000100000010000010000100010010
1100000000000001100000000000011000000000000110000000000011000000000011000000000110000000011000000011000000110000011000011000110011011
1110000000000001110000000000011100000000000111000000000011100000000011100000000111000000011100000011100000111000011100011100111011111
1111000000000001111000000000011110000000000111100000000011110000000011110000000111100000011110000011110000111100011110011110111111111
1111100000000001111100000000011111000000000111110000000011111000000011111000000111110000011111000011111000111110011111011111111111111
1111110000000001111110000000011111100000000111111000000011111100000011111100000111111000011111100011111100111111011111111111111111111
1111111000000001111111000000011111110000000111111100000011111110000011111110000111111100011111110011111110111111111111111111111111111
1111111100000001111111100000011111111000000111111110000011111111000011111111000111111110011111111011111111111111111111111111111111111
1111111110000001111111110000011111111100000111111111000011111111100011111111100111111111011111111111111111111111111111111111111111111
1111111111000001111111111000011111111110000111111111100011111111110011111111110111111111111111111111111111111111111111111111111111111
1111111111100001111111111100011111111111000111111111110011111111111011111111111111111111111111111111111111111111111111111111111111111
1111111111110001111111111110011111111111100111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111001111111111111011111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Integer: 5444684034376312377319904082902529876242 - Left-adjacent-bits: up to 15
000000000000001000000000000001000000000000010000000000000100000000000010000000000010000000000100000000010000000010000000100000010000010000100010010
000000000000011000000000000011000000000000110000000000001100000000000110000000000110000000001100000000110000000110000001100000110000110001100110110
000000000000111000000000000111000000000001110000000000011100000000001110000000001110000000011100000001110000001110000011100001110001110011101111110
000000000001111000000000001111000000000011110000000000111100000000011110000000011110000000111100000011110000011110000111100011110011110111111111110
000000000011111000000000011111000000000111110000000001111100000000111110000000111110000001111100000111110000111110001111100111110111111111111111110
000000000111111000000000111111000000001111110000000011111100000001111110000001111110000011111100001111110001111110011111101111111111111111111111110
000000001111111000000001111111000000011111110000000111111100000011111110000011111110000111111100011111110011111110111111111111111111111111111111110
000000011111111000000011111111000000111111110000001111111100000111111110000111111110001111111100111111110111111111111111111111111111111111111111110
000000111111111000000111111111000001111111110000011111111100001111111110001111111110011111111101111111111111111111111111111111111111111111111111110
000001111111111000001111111111000011111111110000111111111100011111111110011111111110111111111111111111111111111111111111111111111111111111111111110
000011111111111000011111111111000111111111110001111111111100111111111110111111111111111111111111111111111111111111111111111111111111111111111111110
000111111111111000111111111111001111111111110011111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
001111111111111001111111111111011111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
011111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110