<commit_before>

"""
The following set of functions allows us to use `int` objects as predicates,
namely they represent a set of boolean when we write them in binary.

Consider a predicate over six elements, true for those in position 1 and 5, 
namely the second and last elements, respectively.
>>> 0b100010
34

the other way, with `bin` we can take the set representation as a string object:
>>> bin(34)
'0b100010'

Multiply and divide by powers of 2, it is the same to insert and remove objects from 
the set or, in parallel, discard elements for which the predicate has no more sense:
>>> S = 0b100010
>>> S <<= 1
>>> S, bin(S)
(68, '0b1000100')
>>> S >>= 2
>>> S, bin(S)
(17, '0b10001')

"""

import math

def set_bit(S, j): 
    """
    Return a new set from set `S` with element in position `j` turned on.

    Examples
    ========

    Set/turn on the 3-th item of the set:
    >>> S = 0b100010
    >>> bin(set_bit(S, 3))
    '0b101010'

    """
    return S | (1 << j)

def is_on(S, j, return_int=False): 
    """
    Returns `True` if the `j`-th item of the set `S` is on.

    Examples
    ========

    Check if the 3-th and then 2-nd item of the set is on:
    >>> S = 0b101010
    >>> is_on(S, 3), is_on(S, 2)
    (True, False)

    """
    res = S & (1 << j)
    return res if return_int else bool(res)

def clear_bit(S, j):
    """
    Returns a new set from set `S` with the `j`-th item turned off.

    Examples
    ========

    Clear/turn off item in position 1 of the set:
    >>> S = 0b101010
    >>> bin(clear_bit(S, 1))
    '0b101000'

    """
    return S & ~(1 << j)

def toggle_bit(S, j):
    """
    Returns a new set from set `S` with the j-th item toggled (flip the status of).

    Examples
    ========

    Toggle the 2-nd item and then 3-rd item of the set
    >>> S = int('0b101000', base=2)
    >>> S = toggle_bit(S, 2)
    >>> S = toggle_bit(S, 3)
    >>> bin(S)
    '0b100100'

    """
    return S ^ (1 << j)

def low_bit(S): 
    return S & (-S)

def set_all(n):
    return (1 << n) - 1

def modulo(S, N):
    '''
    Returns S % N, where N is a power of 2
    '''
    return S & (N - 1)

def is_power_of_two(S):
    return False if S & (S - 1) else True

def nearest_power_of_two(S):
    return math.floor(2**(math.log2(S) + .5))

def turn_off_last_bit(S):
    return S & (S - 1)

def turn_on_last_zero(S): 
    return S | (S + 1)

def turn_off_last_consecutive_bits(S):
    return S & (S + 1)

def turn_on_last_consecutive_zeroes(S):
    return S | (S - 1)

#_______________________________________________________________________

def gray_code(k): 
    g = k ^ (k >> 1)
    return g

def gray_position(g):
    k=0
    for i in reversed(range(g.bit_length())):
        k ^= all_on(i+1) * is_on(g, i)
    return k

def gray_codes(length=None, justified=False):
    """<commit_msg>Implements auxiliary functions about bit manipulation that allows to switch representation from integers to masks and viceversa.<commit_after>

"""
The following set of functions allows us to use `int` objects as predicates,
namely they represent a set of boolean when we write them in binary.

Consider a predicate over six elements, true for those in position 1 and 5, 
namely the second and last elements, respectively.
>>> 0b100010
34

the other way, with `bin` we can take the set representation as a string object:
>>> bin(34)
'0b100010'

Multiply and divide by powers of 2, it is the same to insert and remove objects from 
the set or, in parallel, discard elements for which the predicate has no more sense:
>>> S = 0b100010
>>> S <<= 1
>>> S, bin(S)
(68, '0b1000100')
>>> S >>= 2
>>> S, bin(S)
(17, '0b10001')

"""


def from_mask(m, coding='big'):
    """
    Returns the integer represented by the bit mask `m`, given in `coding` scheme.

    Keyword argument `coding` represent the coding scheme used by mask `m`, it 
    resembles keyword `byteorder` in function `int.to_bytes`. If it is 'big', then
    a `big endian` scheme has been applied, namely bits at the *beginning* of `m` are the 
    most significant bits of the returned integer; otherwise a `little endian` scheme applies, 
    namely bits at the *end* of the given mask `m` are most significant bits of the
    returned integer.

    Examples
    ========

    >>> from_mask((1,1,0,0), coding='big')
    12

    >>> from_mask((0,0,1,1), coding='little')
    12
    """
    digits = m if coding == 'big' else reversed(m)
    return int('0b'+''.join(map(str, digits)), base=2)

def as_mask(n, coding='big'):
    """
    Returns `n` as a bit mask, namely an iterable of bits, according to `coding` scheme.

    Keyword argument `coding` represent the coding scheme used to build the mask, it 
    resembles keyword `byteorder` in function `int.to_bytes`. If it is 'big', then
    a `big endian` scheme is applied, namely most significant bits of `n` are at 
    the *beginning* of the returned mask; otherwise a `little endian` scheme applies, 
    namely most significant bits of `n` are at the *end* of the returned mask.

    Examples
    ========

    >>> as_mask(12, coding='big')
    (1, 1, 0, 0)

    >>> as_mask(12, coding='little')
    (0, 0, 1, 1)

    """
    m = map(int, bin(n)[2:])
    return tuple(m if coding == 'big' else reversed(list(m)))

def ones(S):
    """
    Returns the positions of bits 1 in S, seen as a mask.

    The returned iterable can be interpreted as the set of 
    elements for which *predicate* `S` holds among `S.bit_length()`
    objects; eventually, it identifies a subset.

    Examples
    ========

    >>> ones(12)
    [2, 3]

    >>> ones(int(0b1000101010))
    [1, 3, 5, 9]

    """

    mask = as_mask(S, coding='little')
    return [i for i, m in enumerate(mask) if m]

def set_bit(S, j): 
    """
    Return a new set from set `S` with element in position `j` turned on.

    Examples
    ========

    Set/turn on the 3-th item of the set:
    >>> S = 0b100010
    >>> bin(set_bit(S, 3))
    '0b101010'

    """
    return S | (1 << j)

def is_on(S, j, return_int=False): 
    """
    Returns `True` if the `j`-th item of the set `S` is on.

    Examples
    ========

    Check if the 3-th and then 2-nd item of the set is on:
    >>> S = 0b101010
    >>> is_on(S, 3), is_on(S, 2)
    (True, False)

    """
    res = S & (1 << j)
    return res if return_int else bool(res)

def clear_bit(S, j):
    """
    Returns a new set from set `S` with the `j`-th item turned off.

    Examples
    ========

    Clear/turn off item in position 1 of the set:
    >>> S = 0b101010
    >>> bin(clear_bit(S, 1))
    '0b101000'

    """
    return S & ~(1 << j)

def toggle_bit(S, j):
    """
    Returns a new set from set `S` with the j-th item toggled (flip the status of).

    Examples
    ========

    Toggle the 2-nd item and then 3-rd item of the set
    >>> S = int('0b101000', base=2)
    >>> S = toggle_bit(S, 2)
    >>> S = toggle_bit(S, 3)
    >>> bin(S)
    '0b100100'

    """
    return S ^ (1 << j)

def low_bit(S): 
    return S & (-S)

def set_all(n):
    return (1 << n) - 1

def modulo(S, N):
    '''
    Returns S % N, where N is a power of 2
    '''
    return S & (N - 1)

def is_power_of_two(S):
    return False if S & (S - 1) else True

def nearest_power_of_two(S):

    import math
    return math.floor(2**(math.log2(S) + .5))

def turn_off_last_bit(S):
    return S & (S - 1)

def turn_on_last_zero(S): 
    return S | (S + 1)

def turn_off_last_consecutive_bits(S):
    return S & (S + 1)

def turn_on_last_consecutive_zeroes(S):
    return S | (S - 1)

#_______________________________________________________________________

def gray_code(k): 
    """

    Examples
    ========

    >>> bin(gray_code(0b101100110))
    '0b111010101'

    """
    g = k ^ (k >> 1)
    return g

def gray_position(g):
    """

    Examples
    ========

    >>> bin(gray_position(0b111010101))
    '0b101100110'

    """
    k=0
    for i in reversed(range(g.bit_length())):
        k ^= set_all(i+1) * is_on(g, i)
    return k

def gray_codes(length=None, justified=False):
    """
{'fraction_non_alphanumeric': 0.14010202811994527, 'fraction_numerical': 0.0429264650989175, 'mean_word_length': 2.7701688555347093, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 137, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3667019', 'n_tokens_mistral': 3113, 'n_tokens_neox': 2766, 'n_words': 1030}