Set right-adjacent bits
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 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
}
- 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 var i = 0 while (i < 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 } } i = i + 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 = test[0].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