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.

F#

<lang fsharp> // Set right-adjacent bits. Nigel Galloway: December 21st., 2021 let fN g l=let rec fG n g=[|match n,g with ('0'::t,0)->yield '0'; yield! fG t 0

                                         |('0'::t,n)->yield '1'; yield! fG t (n-1)
                                         |(_::t,_)  ->yield '1'; yield! fG t l
                                         |_         ->()|]
          fG (g|>List.ofSeq) 0|>System.String

[("1000",2);("0100",2);("0010",2);("0001",2);("0000",2);("010000000000100000000010000000010000000100000010000010000100010010",0);("010000000000100000000010000000010000000100000010000010000100010010",1);("010000000000100000000010000000010000000100000010000010000100010010",2);("010000000000100000000010000000010000000100000010000010000100010010",3)]|>List.iter(fun(n,g)->printfn "%s\n%s" n (fN n g)) </lang>

Output:

1000
1110
0100
0111
0010
0011
0001
0001
0000
0000
010000000000100000000010000000010000000100000010000010000100010010
010000000000100000000010000000010000000100000010000010000100010010
010000000000100000000010000000010000000100000010000010000100010010
011000000000110000000011000000011000000110000011000011000110011011
010000000000100000000010000000010000000100000010000010000100010010
011100000000111000000011100000011100000111000011100011100111011111
010000000000100000000010000000010000000100000010000010000100010010
011110000000111100000011110000011110000111100011110011110111111111

Perl

<lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Set_right-adjacent_bits use warnings;

while( )

 {
 my ($n, $input) = split;
 my $width = length $input;
 my $result = ;
 $result |= substr 0 x $_ . $input, 0, $width for 0 .. $n;
 print "n = $n  width = $width\n input $input\nresult $result\n\n";
 }

__DATA__ 2 1000 2 0100 2 0011 2 0000 0 010000000000100000000010000000010000000100000010000010000100010010 1 010000000000100000000010000000010000000100000010000010000100010010 2 010000000000100000000010000000010000000100000010000010000100010010 3 010000000000100000000010000000010000000100000010000010000100010010</lang>

Output:

n = 2  width = 4
 input 1000
result 1110

n = 2  width = 4
 input 0100
result 0111

n = 2  width = 4
 input 0011
result 0011

n = 2  width = 4
 input 0000
result 0000

n = 0  width = 66
 input 010000000000100000000010000000010000000100000010000010000100010010
result 010000000000100000000010000000010000000100000010000010000100010010

n = 1  width = 66
 input 010000000000100000000010000000010000000100000010000010000100010010
result 011000000000110000000011000000011000000110000011000011000110011011

n = 2  width = 66
 input 010000000000100000000010000000010000000100000010000010000100010010
result 011100000000111000000011100000011100000111000011100011100111011111

n = 3  width = 66
 input 010000000000100000000010000000010000000100000010000010000100010010
result 011110000000111100000011110000011110000111100011110011110111111111

Phix

The basic idea is to create a mask of n 1s on the right and either shift that left or (a copy of) the input right, and use it to determine which bits of the result need to be set, in addition to the originals. The string version actually uses a count of 1s instead of an actual mask, and obviously the odd() and even() functions work just as well on the characters '0' and '1' as they do the numbers/bits 0 and 1. Note that both the string and mpz versions propagate any number of bits in a single pass, in other words explicitly iterating down all the input bits as opposed to implicitly setting all those bits n times, albeit the latter is probably a smidge faster.

string

with javascript_semantics
function str_srb(string input, integer n)
    string res = input
    integer l = length(input),
            m = min(n,l),
            count = sum(sq_eq(input[-m..-1],'1')),
            k = l-n
    for i=l to 1 by -1 do
        integer bit = odd(input[i])
        count += iff(k>0?odd(input[k]):0)-bit
        if count and not bit then res[i] = '1' end if
        k -= 1
    end for
    assert(count=0)
    return res
end function

constant tests = {{"1000",2,2},{"0100",2,2},{"0010",2,2},{"0000",2,2},
                  {"010000000000100000000010000000010000000100000010000010000100010010",0,3}}

for i=1 to length(tests) do
    {string input, integer l, integer m} = tests[i]
    printf(1,"input: %s (width %d)\n",{input,length(input)})
    for n=l to m do
        printf(1,"n = %d: %s\n",{n,str_srb(input,n)})
    end for
end for

Output:

input: 1000 (width 4)
n = 2: 1110
input: 0100 (width 4)
n = 2: 0111
input: 0010 (width 4)
n = 2: 0011
input: 0000 (width 4)
n = 2: 0000
input: 010000000000100000000010000000010000000100000010000010000100010010 (width 66)
n = 0: 010000000000100000000010000000010000000100000010000010000100010010
n = 1: 011000000000110000000011000000011000000110000011000011000110011011
n = 2: 011100000000111000000011100000011100000111000011100011100111011111
n = 3: 011110000000111100000011110000011110000111100011110011110111111111

mpz

identical output

with javascript_semantics
include mpfr.e
function mpz_srb(string input, integer n)
    mpz res = mpz_init("0b"&input),
        tmp = mpz_init_set(res),
        bit = mpz_init(1),
       mask = mpz_init(power(2,n+1)-1),
       rask = mpz_init() -- (mask res)
    for i=1 to length(input) do -- (backward, actually)
        if mpz_even(tmp) then
            mpz_and(rask,tmp,mask)
            if mpz_cmp_si(rask,0)!=0 then
                mpz_add(res,res,bit)
            end if
        end if
        mpz_mul_2exp(bit, bit, 1)    -- aka left shift
        mpz_fdiv_q_2exp(tmp, tmp, 1) -- aka right shift
    end for
    string ret = mpz_get_str(res,2)
    integer lz = length(input)-length(ret)
    if lz then ret = repeat('0',lz)&ret end if
    return ret
end function    
--...
        printf(1,"n = %d: %s\n",{n,mpz_srb(input,n)})

hybrid

Makes it even simpler, again identical output

with javascript_semantics
include mpfr.e
function mpz_srb(string input, integer n)
    string res = input
    mpz tmp = mpz_init("0b"&input),
       mask = mpz_init(power(2,n+1)-1),
       rask = mpz_init() -- (mask res)
    for i=length(input) to 1 by -1 do
        if input[i]='0' then
            mpz_and(rask,tmp,mask)
            if mpz_cmp_si(rask,0)!=0 then
                res[i] = '1'
            end if
        end if
        mpz_fdiv_q_2exp(tmp, tmp, 1) -- aka right shift
    end for
    return res
end function    
--...
        printf(1,"n = %d: %s\n",{n,mpz_srb(input,n)})

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

This example is incomplete. Missing the examples asked for Please ensure that it meets all task requirements and remove this message.

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

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

   my $m = $n;
   $m +|= ($n +> $_) for ^$b;
   $m

}

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

   my $m = $n;
   $m +|= ($n +< $_) for ^$b;
   $m

}

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

Wren

Using a list of 0's and 1's so we don't have to resort to BigInt. <lang ecmascript>var setRightBits = Fn.new { |bits, e, n|

   if (e == 0 || n <= 0) return bits
   var bits2 = bits.toList
   for (i in 0...e - 1) {
       var c = bits[i]
       if (c == 1) {
           var j = i + 1
           while (j <= i + n && j < e) {
               bits2[j] = 1
               j = j + 1
           }
       }
   }
   return bits2

}

var b = "010000000000100000000010000000010000000100000010000010000100010010" var tests = [["1000", 2], ["0100", 2], ["0010", 2], ["0000", 2], [b, 0], [b, 1], [b, 2], [b, 3]] for (test in tests) {

   var bits = test[0]
   var e = bits.count
   var n = test[1]
   System.print("n = %(n); Width e = %(e):")
   System.print("    Input b: %(bits)")
   bits = bits.map { |c| c.bytes[0] - 48 }.toList
   bits = setRightBits.call(bits, e, n)
   System.print("     Result: %(bits.join())\n")

}</lang>

Output:

n = 2; Width e = 4:
    Input b: 1000
     Result: 1110

n = 2; Width e = 4:
    Input b: 0100
     Result: 0111

n = 2; Width e = 4:
    Input b: 0010
     Result: 0011

n = 2; Width e = 4:
    Input b: 0000
     Result: 0000

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