Bit primitives

concrete_fhe_toolkit.math.bits

Bit-level LUT primitives for Concrete FHE arithmetic circuits.

All bit lists in this module are little-endian: index 0 is the least significant bit. The primitives are intentionally tiny traceable building blocks, so they can be used on clear bits for tests or on encrypted bit expressions while compiling larger Concrete circuits.

bit_not

bit_not(bit: Any) -> Any

Return NOT(bit) for a bit expression.

Parameters:

Name	Type	Description	Default
bit	Any	The bit expression to negate.	required

Returns:

Name	Type	Description
Any	Any	The negated bit expression.

Example

from concrete_fhe_toolkit.math.bits import bit_not

print(bit_not(1))  # 0

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_not(bit: Any) -> Any:
    """Return NOT(bit) for a bit expression.

    Args:
        bit (Any): The bit expression to negate.

    Returns:
        Any: The negated bit expression.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_not

        print(bit_not(1))  # 0
        ```
    """
    return BIT_NOT_LUT[bit]

bit_and

bit_and(left: Any, right: Any) -> Any

Return left AND right for bit expressions.

Parameters:

Name	Type	Description	Default
left	Any	The left encrypted operand.	required
right	Any	The right encrypted operand.	required

Returns:

Name	Type	Description
Any	Any	The result of left AND right.

Example

from concrete_fhe_toolkit.math.bits import bit_and

print(bit_and(1, 0))  # 0

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_and(left: Any, right: Any) -> Any:
    """Return left AND right for bit expressions.

    Args:
        left (Any): The left encrypted operand.
        right (Any): The right encrypted operand.

    Returns:
        Any: The result of left AND right.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_and

        print(bit_and(1, 0))  # 0
        ```
    """
    return BIT_AND_LUT[2 * left + right]

bit_or

bit_or(left: Any, right: Any) -> Any

Return left OR right for bit expressions.

Parameters:

Name	Type	Description	Default
left	Any	The left encrypted operand.	required
right	Any	The right encrypted operand.	required

Returns:

Name	Type	Description
Any	Any	The result of left OR right.

Example

from concrete_fhe_toolkit.math.bits import bit_or

print(bit_or(1, 0))  # 1

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_or(left: Any, right: Any) -> Any:
    """Return left OR right for bit expressions.

    Args:
        left (Any): The left encrypted operand.
        right (Any): The right encrypted operand.

    Returns:
        Any: The result of left OR right.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_or

        print(bit_or(1, 0))  # 1
        ```
    """
    return BIT_OR_LUT[2 * left + right]

bit_xor

bit_xor(left: Any, right: Any) -> Any

Return left XOR right for bit expressions.

Parameters:

Name	Type	Description	Default
left	Any	The left encrypted operand.	required
right	Any	The right encrypted operand.	required

Returns:

Name	Type	Description
Any	Any	The result of left XOR right.

Example

from concrete_fhe_toolkit.math.bits import bit_xor

print(bit_xor(1, 1))  # 0

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_xor(left: Any, right: Any) -> Any:
    """Return left XOR right for bit expressions.

    Args:
        left (Any): The left encrypted operand.
        right (Any): The right encrypted operand.

    Returns:
        Any: The result of left XOR right.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_xor

        print(bit_xor(1, 1))  # 0
        ```
    """
    return BIT_XOR_LUT[2 * left + right]

bit_select

bit_select(control: Any, when_one: Any, when_zero: Any) -> Any

Return when_one if control is 1, otherwise when_zero.

Parameters:

Name	Type	Description	Default
control	Any	The control bit.	required
when_one	Any	The value to return if control is 1.	required
when_zero	Any	The value to return if control is 0.	required

Returns:

Name	Type	Description
Any	Any	The selected value.

Example

from concrete_fhe_toolkit.math.bits import bit_select

print(bit_select(control=1, when_one=5, when_zero=10))  # 5

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_select(control: Any, when_one: Any, when_zero: Any) -> Any:
    """Return when_one if control is 1, otherwise when_zero.

    Args:
        control (Any): The control bit.
        when_one (Any): The value to return if control is 1.
        when_zero (Any): The value to return if control is 0.

    Returns:
        Any: The selected value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_select

        print(bit_select(control=1, when_one=5, when_zero=10))  # 5
        ```
    """
    return BIT_SELECT_LUT[4 * control + 2 * when_one + when_zero]

full_adder_bit

full_adder_bit(left: Any, right: Any, carry_in: Any) -> tuple[Any, Any]

Return (sum_bit, carry_out) for one full-adder stage.

Parameters:

Name	Type	Description	Default
left	Any	The left encrypted operand.	required
right	Any	The right encrypted operand.	required
carry_in	Any	The carry-in bit.	required

Returns:

Type	Description
tuple[Any, Any]	tuple[Any, Any]: A tuple containing the sum bit and the carry-out bit.

Example

from concrete_fhe_toolkit.math.bits import full_adder_bit

print(full_adder_bit(1, 1, 0))  # (0, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

def full_adder_bit(left: Any, right: Any, carry_in: Any) -> tuple[Any, Any]:
    """Return (sum_bit, carry_out) for one full-adder stage.

    Args:
        left (Any): The left encrypted operand.
        right (Any): The right encrypted operand.
        carry_in (Any): The carry-in bit.

    Returns:
        tuple[Any, Any]: A tuple containing the sum bit and the carry-out bit.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import full_adder_bit

        print(full_adder_bit(1, 1, 0))  # (0, 1)
        ```
    """
    address = 4 * left + 2 * right + carry_in
    return FULL_ADDER_SUM_LUT[address], FULL_ADDER_CARRY_LUT[address]

full_subtractor_bit

full_subtractor_bit(left: Any, right: Any, borrow_in: Any) -> tuple[Any, Any]

Return (difference_bit, borrow_out) for one full-subtractor stage.

Parameters:

Name	Type	Description	Default
left	Any	The left encrypted operand.	required
right	Any	The right encrypted operand.	required
borrow_in	Any	The borrow-in bit.	required

Returns:

Type	Description
tuple[Any, Any]	tuple[Any, Any]: A tuple containing the difference bit and the borrow-out bit.

Example

from concrete_fhe_toolkit.math.bits import full_subtractor_bit

print(full_subtractor_bit(0, 1, 0))  # (1, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

def full_subtractor_bit(left: Any, right: Any, borrow_in: Any) -> tuple[Any, Any]:
    """Return (difference_bit, borrow_out) for one full-subtractor stage.

    Args:
        left (Any): The left encrypted operand.
        right (Any): The right encrypted operand.
        borrow_in (Any): The borrow-in bit.

    Returns:
        tuple[Any, Any]: A tuple containing the difference bit and the borrow-out bit.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import full_subtractor_bit

        print(full_subtractor_bit(0, 1, 0))  # (1, 1)
        ```
    """
    address = 4 * left + 2 * right + borrow_in
    return FULL_SUBTRACTOR_DIFF_LUT[address], FULL_SUBTRACTOR_BORROW_LUT[address]

bit_or_many

bit_or_many(bits: Iterable[Any]) -> Any

Return the OR-reduction of a bit iterable with higher performance.

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bits to OR-reduce.	required

Returns:

Name	Type	Description
Any	Any	The result of the OR-reduction.

Example

from concrete_fhe_toolkit.math.bits import bit_or_many

print(bit_or_many([0, 1, 0]))  # 1

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_or_many(bits: Iterable[Any]) -> Any:
    """Return the OR-reduction of a bit iterable with higher performance.

    Args:
        bits (Iterable[Any]): The bits to OR-reduce.

    Returns:
        Any: The result of the OR-reduction.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_or_many

        print(bit_or_many([0, 1, 0]))  # 1
        ```
    """
    result = _bit_op_many(bits,bit_or)
    return result 

bit_and_many

bit_and_many(bits: Iterable[Any]) -> Any

Return the AND-reduction of a bit iterable with higher performance.

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bits to AND-reduce.	required

Returns:

Name	Type	Description
Any	Any	The result of the AND-reduction.

Example

from concrete_fhe_toolkit.math.bits import bit_and_many

print(bit_and_many([1, 1, 1]))  # 1

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_and_many(bits: Iterable[Any]) -> Any:
    """Return the AND-reduction of a bit iterable with higher performance.

    Args:
        bits (Iterable[Any]): The bits to AND-reduce.

    Returns:
        Any: The result of the AND-reduction.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_and_many

        print(bit_and_many([1, 1, 1]))  # 1
        ```
    """
    result = _bit_op_many(bits,bit_and)
    return result  

bit_xor_many

bit_xor_many(bits: Iterable[Any]) -> Any

Return the XOR-reduction of a bit iterable with higher performance.

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bits to XOR-reduce.	required

Returns:

Name	Type	Description
Any	Any	The result of the XOR-reduction.

Example

from concrete_fhe_toolkit.math.bits import bit_xor_many

print(bit_xor_many([1, 1, 1]))  # 1

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_xor_many(bits: Iterable[Any]) -> Any:
    """Return the XOR-reduction of a bit iterable with higher performance.

    Args:
        bits (Iterable[Any]): The bits to XOR-reduce.

    Returns:
        Any: The result of the XOR-reduction.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_xor_many

        print(bit_xor_many([1, 1, 1]))  # 1
        ```
    """
    result = _bit_op_many(bits,bit_xor)
    return result       

integer_to_bits

integer_to_bits(value: Any, width: int) -> tuple[Any, ...]

Return little-endian bits of an unsigned integer expression.

Parameters:

Name	Type	Description	Default
value	Any	The encrypted value to process or validate.	required
width	int	The fixed bit width.	required

Returns:

Type	Description
tuple[Any, ...]	tuple[Any, ...]: The little-endian bits.

Example

from concrete_fhe_toolkit.math.bits import integer_to_bits

print(integer_to_bits(6, width=3))  # (0, 1, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

def integer_to_bits(value: Any, width: int) -> tuple[Any, ...]:
    """Return little-endian bits of an unsigned integer expression.

    Args:
        value (Any): The encrypted value to process or validate.
        width (int): The fixed bit width.

    Returns:
        tuple[Any, ...]: The little-endian bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import integer_to_bits

        print(integer_to_bits(6, width=3))  # (0, 1, 1)
        ```
    """
    normalized_width = _bit_width(width)
    return tuple((value >> index) & 1 for index in range(normalized_width))

bits_to_unsigned

bits_to_unsigned(bits: Iterable[Any]) -> Any

Convert little-endian bits to an unsigned integer expression.

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The little-endian bits.	required

Returns:

Name	Type	Description
Any	Any	The unsigned integer expression.

Example

from concrete_fhe_toolkit.math.bits import bits_to_unsigned

print(bits_to_unsigned([0, 1, 1]))  # 6

Source code in src/concrete_fhe_toolkit/math/bits.py

def bits_to_unsigned(bits: Iterable[Any]) -> Any:
    """Convert little-endian bits to an unsigned integer expression.

    Args:
        bits (Iterable[Any]): The little-endian bits.

    Returns:
        Any: The unsigned integer expression.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bits_to_unsigned

        print(bits_to_unsigned([0, 1, 1]))  # 6
        ```
    """
    result: Any = 0
    for index, bit in enumerate(bits):
        result = result + bit * (1 << index)
    return result

unsigned_to_bits

unsigned_to_bits(value: int, width: int) -> tuple[int, ...]

Return little-endian bits of a clear unsigned integer constant.

Parameters:

Name	Type	Description	Default
value	int	The encrypted value to process or validate.	required
width	int	The fixed bit width.	required

Returns:

Type	Description
tuple[int, ...]	tuple[int, ...]: The little-endian bits.

Example

from concrete_fhe_toolkit.math.bits import unsigned_to_bits

print(unsigned_to_bits(6, width=3))  # (0, 1, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

@client_side_helper
def unsigned_to_bits(value: int, width: int) -> tuple[int, ...]:
    """Return little-endian bits of a clear unsigned integer constant.

    Args:
        value (int): The encrypted value to process or validate.
        width (int): The fixed bit width.

    Returns:
        tuple[int, ...]: The little-endian bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import unsigned_to_bits

        print(unsigned_to_bits(6, width=3))  # (0, 1, 1)
        ```
    """
    normalized_width = _bit_width(width)
    normalized_value = validate_integer("value", value, minimum=0)
    if normalized_value >= (1 << normalized_width):
        raise ValueError("value does not fit in width bits")
    return tuple((normalized_value >> index) & 1 for index in range(normalized_width))

twos_complement_bits

twos_complement_bits(value: int, width: int) -> tuple[int, ...]

Return little-endian two's-complement bits for a clear signed integer.

Parameters:

Name	Type	Description	Default
value	int	The encrypted value to process or validate.	required
width	int	The fixed bit width.	required

Returns:

Type	Description
tuple[int, ...]	tuple[int, ...]: The little-endian bits.

Example

from concrete_fhe_toolkit.math.bits import twos_complement_bits

print(twos_complement_bits(-2, width=3))  # (0, 1, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

@client_side_helper
def twos_complement_bits(value: int, width: int) -> tuple[int, ...]:
    """Return little-endian two's-complement bits for a clear signed integer.

    Args:
        value (int): The encrypted value to process or validate.
        width (int): The fixed bit width.

    Returns:
        tuple[int, ...]: The little-endian bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import twos_complement_bits

        print(twos_complement_bits(-2, width=3))  # (0, 1, 1)
        ```
    """
    normalized_width = _bit_width(width)
    normalized_value = validate_integer("value", value)
    minimum = -(1 << (normalized_width - 1))
    maximum = (1 << (normalized_width - 1)) - 1
    if not minimum <= normalized_value <= maximum:
        raise ValueError(f"value must fit in signed {normalized_width}-bit range")
    if normalized_value < 0:
        normalized_value = (1 << normalized_width) + normalized_value
    return tuple((normalized_value >> index) & 1 for index in range(normalized_width))

sign_magnitude_to_twos_complement_bits

sign_magnitude_to_twos_complement_bits(magnitude_bits: Iterable[Any], sign_bit: Any, width: int | None = None) -> tuple[Any, ...]

Convert sign-magnitude bits to two's-complement bits.

The output width is one bit wider than the magnitude width so the sign can be represented safely.

Parameters:

Name	Type	Description	Default
magnitude_bits	Iterable[Any]	The magnitude bits.	required
sign_bit	Any	The sign bit.	required
width	int | None	The fixed bit width.	None

Returns:

Type	Description
tuple[Any, ...]	tuple[Any, ...]: The two's-complement bits.

Example

from concrete_fhe_toolkit.math.bits import sign_magnitude_to_twos_complement_bits

# Magnitude 2 (0, 1) and negative sign (1) -> -2 in two's complement
print(sign_magnitude_to_twos_complement_bits([0, 1], sign_bit=1))  # (0, 1, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

def sign_magnitude_to_twos_complement_bits(
    magnitude_bits: Iterable[Any],
    sign_bit: Any,
    width: int | None = None,
) -> tuple[Any, ...]:
    """Convert sign-magnitude bits to two's-complement bits.

    The output width is one bit wider than the magnitude width so the sign can
    be represented safely.

    Args:
        magnitude_bits (Iterable[Any]): The magnitude bits.
        sign_bit (Any): The sign bit.
        width (int | None, optional): The fixed bit width.

    Returns:
        tuple[Any, ...]: The two's-complement bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import sign_magnitude_to_twos_complement_bits

        # Magnitude 2 (0, 1) and negative sign (1) -> -2 in two's complement
        print(sign_magnitude_to_twos_complement_bits([0, 1], sign_bit=1))  # (0, 1, 1)
        ```
    """
    bits = tuple(magnitude_bits)
    if not bits:
        raise ValueError("magnitude_bits must contain at least one bit")
    normalized_width = len(bits) if width is None else _bit_width(width)
    if len(bits) < normalized_width:
        bits = bits + (0,) * (normalized_width - len(bits))
    elif len(bits) > normalized_width:
        raise ValueError("magnitude_bits is longer than width")

    flipped = tuple(bit_xor(bit, sign_bit) for bit in bits)
    output: list[Any] = []
    carry = sign_bit
    for bit in flipped:
        result_bit, carry = full_adder_bit(bit, 0, carry)
        output.append(result_bit)
    output.append(sign_bit)

    magnitude_nonzero = bit_or_many(bits)
    return tuple(bit_select(magnitude_nonzero, bit, 0) for bit in output)

twos_complement_add_bits

twos_complement_add_bits(left_bits: Iterable[Any], right_bits: Iterable[Any], width: int) -> tuple[Any, ...]

Add two two's-complement bit lists modulo 2**width.

Parameters:

Name	Type	Description	Default
left_bits	Iterable[Any]	The first two's-complement bit list.	required
right_bits	Iterable[Any]	The second two's-complement bit list.	required
width	int	The fixed bit width.	required

Returns:

Type	Description
tuple[Any, ...]	tuple[Any, ...]: The sum as a two's-complement bit list.

Example

from concrete_fhe_toolkit.math.bits import twos_complement_add_bits

# 1 + (-2) = -1
# 1 -> (1, 0, 0), -2 -> (0, 1, 1) -> result: (1, 1, 1) -> -1
print(twos_complement_add_bits([1, 0, 0], [0, 1, 1], width=3))

Source code in src/concrete_fhe_toolkit/math/bits.py

def twos_complement_add_bits(
    left_bits: Iterable[Any],
    right_bits: Iterable[Any],
    width: int,
) -> tuple[Any, ...]:
    """Add two two's-complement bit lists modulo 2**width.

    Args:
        left_bits (Iterable[Any]): The first two's-complement bit list.
        right_bits (Iterable[Any]): The second two's-complement bit list.
        width (int): The fixed bit width.

    Returns:
        tuple[Any, ...]: The sum as a two's-complement bit list.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import twos_complement_add_bits

        # 1 + (-2) = -1
        # 1 -> (1, 0, 0), -2 -> (0, 1, 1) -> result: (1, 1, 1) -> -1
        print(twos_complement_add_bits([1, 0, 0], [0, 1, 1], width=3))
        ```
    """
    normalized_width = _bit_width(width)
    left = tuple(left_bits)
    right = tuple(right_bits)
    left_sign = left[-1] if left else 0
    right_sign = right[-1] if right else 0
    padded_left_bits = []
    padded_right_bits = []

    for index in range(normalized_width):
        padded_left_bits.append(left[index] if index < len(left) else left_sign)
        padded_right_bits.append(right[index] if index < len(right) else right_sign)

    G = [bit_and(padded_left_bits[i],padded_right_bits[i]) for i in range(normalized_width)]
    P = [bit_xor(padded_left_bits[i],padded_right_bits[i]) for i in range(normalized_width)]
    original_P = list(P)
    step = 1

    while step<normalized_width:
        next_G = []
        next_P = []
        for i in range(normalized_width):
            if(i < step):
                next_G.append(G[i])
                next_P.append(P[i])
            else:
                next_G.append(bit_or(G[i],bit_and(P[i],G[i-step])))
                next_P.append(bit_and(P[i],P[i-step]))

        G = next_G
        P = next_P   
        step*=2                 

    result: list[Any] = [original_P[0]]
    for i in range(1,normalized_width):
        result.append(bit_xor(original_P[i],G[i-1]))
    return tuple(result)

twos_complement_multiply_by_constant_bits

twos_complement_multiply_by_constant_bits(signed_bits: Iterable[Any], multiplier: int, output_width: int) -> tuple[Any, ...]

Multiply two's-complement bits by a nonnegative clear integer.

Parameters:

Name	Type	Description	Default
signed_bits	Iterable[Any]	The two's-complement bit list.	required
multiplier	int	The nonnegative clear integer multiplier.	required
output_width	int	The output bit width.	required

Returns:

Type	Description
tuple[Any, ...]	tuple[Any, ...]: The product as a two's-complement bit list.

Example

from concrete_fhe_toolkit.math.bits import twos_complement_multiply_by_constant_bits

# -2 -> (0, 1, 1). -2 * 3 = -6 -> (0, 1, 0, 1) in 4-bit
print(twos_complement_multiply_by_constant_bits([0, 1, 1], multiplier=3, output_width=4))

Source code in src/concrete_fhe_toolkit/math/bits.py

def twos_complement_multiply_by_constant_bits(
    signed_bits: Iterable[Any],
    multiplier: int,
    output_width: int,
) -> tuple[Any, ...]:
    """Multiply two's-complement bits by a nonnegative clear integer.

    Args:
        signed_bits (Iterable[Any]): The two's-complement bit list.
        multiplier (int): The nonnegative clear integer multiplier.
        output_width (int): The output bit width.

    Returns:
        tuple[Any, ...]: The product as a two's-complement bit list.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import twos_complement_multiply_by_constant_bits

        # -2 -> (0, 1, 1). -2 * 3 = -6 -> (0, 1, 0, 1) in 4-bit
        print(twos_complement_multiply_by_constant_bits([0, 1, 1], multiplier=3, output_width=4))
        ```
    """
    bits = tuple(signed_bits)
    if not bits:
        raise ValueError("signed_bits must contain at least one bit")
    normalized_multiplier = validate_integer("multiplier", multiplier, minimum=0)
    normalized_output_width = _bit_width(output_width)
    sign_bit = bits[-1]
    result: tuple[Any, ...] = (0,) * normalized_output_width

    for shift in range(normalized_multiplier.bit_length()):
        if (normalized_multiplier >> shift) & 1:
            shifted = (
                (0,) * shift
                + tuple(
                    bits[index] if index < len(bits) else sign_bit
                    for index in range(normalized_output_width - shift)
                )
            )[:normalized_output_width]
            result = twos_complement_add_bits(
                result,
                shifted,
                normalized_output_width,
            )

    return result

multiply_bits

multiply_bits(left_bits: Iterable[Any], right_bits: Iterable[Any], width: int) -> tuple[Any]

Multiply two two's-complement bit lists.

Parameters:

Name	Type	Description	Default
left_bits	Iterable[Any]	The first two's-complement bit list.	required
right_bits	Iterable[Any]	The second two's-complement bit list.	required
width	int	The fixed bit width.	required

Returns:

Type	Description
tuple[Any]	tuple[Any]: The product as a two's-complement bit list.

Example

from concrete_fhe_toolkit.math.bits import multiply_bits

# Used inside an FHE program compilation
res = multiply_bits([0, 1, 1], [0, 1, 0], width=4)

Source code in src/concrete_fhe_toolkit/math/bits.py

def multiply_bits(
    left_bits: Iterable[Any],
    right_bits: Iterable[Any],
    width: int,
)-> tuple[Any]:
    """Multiply two two's-complement bit lists.

    Args:
        left_bits (Iterable[Any]): The first two's-complement bit list.
        right_bits (Iterable[Any]): The second two's-complement bit list.
        width (int): The fixed bit width.

    Returns:
        tuple[Any]: The product as a two's-complement bit list.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import multiply_bits

        # Used inside an FHE program compilation
        res = multiply_bits([0, 1, 1], [0, 1, 0], width=4)
        ```
    """

    left = tuple(left_bits)
    right = tuple(right_bits)

    normalized_width = _bit_width(width)
    padded_left =  left + (left[-1],) * (normalized_width-len(left)) 
    padded_right = right + (right[-1],) * (normalized_width-len(right))
    rows = []

    for index,right_value in enumerate(padded_right):
        new_padded_left = ((0,)*index + padded_left)[:normalized_width]
        row = [bit_and(left_value,right_value) for left_value in new_padded_left]
        rows.append(row)

    product = tuple(rows[0])
    for i in range(1,len(rows)):
        product = twos_complement_add_bits(rows[i],product,width)

    return product    

shift_left_bits

shift_left_bits(bits: Iterable[Any], amount: int) -> tuple

Logical left shift by a public amount; output keeps the input width.

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bits to shift.	required
amount	int	The encrypted integer amount to be processed.	required

Returns:

Name	Type	Description
tuple	tuple	The shifted bits.

Example

from concrete_fhe_toolkit.math.bits import shift_left_bits

print(shift_left_bits([1, 1, 0], amount=1))  # (0, 1, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

def shift_left_bits(bits: Iterable[Any], amount: int) -> tuple:
    """Logical left shift by a public amount; output keeps the input width.

    Args:
        bits (Iterable[Any]): The bits to shift.
        amount (int): The encrypted integer amount to be processed.

    Returns:
        tuple: The shifted bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import shift_left_bits

        print(shift_left_bits([1, 1, 0], amount=1))  # (0, 1, 1)
        ```
    """
    normalized = tuple(bits)
    if not normalized:
        raise ValueError("bits must contain at least one bit")
    shift = validate_integer("amount", amount, minimum=0)
    width = len(normalized)
    return ((0,) * min(shift, width) + normalized)[:width]

shift_right_bits

shift_right_bits(bits: Iterable[Any], amount: int, *, arithmetic: bool = False) -> tuple

Right shift by a public amount; arithmetic=True sign-extends from the MSB.

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bits to shift.	required
amount	int	The encrypted integer amount to be processed.	required
arithmetic	bool	Whether to sign-extend. Defaults to False.	False

Returns:

Name	Type	Description
tuple	tuple	The shifted bits.

Example

from concrete_fhe_toolkit.math.bits import shift_right_bits

print(shift_right_bits([0, 1, 1], amount=1, arithmetic=True))  # (1, 1, 1)

Source code in src/concrete_fhe_toolkit/math/bits.py

def shift_right_bits(
    bits: Iterable[Any],
    amount: int,
    *,
    arithmetic: bool = False,
) -> tuple:
    """Right shift by a public amount; arithmetic=True sign-extends from the MSB.

    Args:
        bits (Iterable[Any]): The bits to shift.
        amount (int): The encrypted integer amount to be processed.
        arithmetic (bool, optional): Whether to sign-extend. Defaults to False.

    Returns:
        tuple: The shifted bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import shift_right_bits

        print(shift_right_bits([0, 1, 1], amount=1, arithmetic=True))  # (1, 1, 1)
        ```
    """
    normalized = tuple(bits)
    if not normalized:
        raise ValueError("bits must contain at least one bit")
    shift = validate_integer("amount", amount, minimum=0)
    width = len(normalized)
    fill = normalized[-1] if arithmetic else 0
    return (normalized[min(shift, width):] + (fill,) * min(shift, width))[:width]

rotate_left_bits

rotate_left_bits(bits: Iterable[Any], amount: int) -> tuple

Rotate toward the MSB by a public amount (little-endian bit lists).

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bits to rotate.	required
amount	int	The encrypted integer amount to be processed.	required

Returns:

Name	Type	Description
tuple	tuple	The rotated bits.

Example

from concrete_fhe_toolkit.math.bits import rotate_left_bits

print(rotate_left_bits([1, 0, 0], amount=1))  # (0, 1, 0)

Source code in src/concrete_fhe_toolkit/math/bits.py

def rotate_left_bits(bits: Iterable[Any], amount: int) -> tuple:
    """Rotate toward the MSB by a public amount (little-endian bit lists).

    Args:
        bits (Iterable[Any]): The bits to rotate.
        amount (int): The encrypted integer amount to be processed.

    Returns:
        tuple: The rotated bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import rotate_left_bits

        print(rotate_left_bits([1, 0, 0], amount=1))  # (0, 1, 0)
        ```
    """
    normalized = tuple(bits)
    if not normalized:
        raise ValueError("bits must contain at least one bit")
    shift = validate_integer("amount", amount, minimum=0) % len(normalized)
    return tuple(
        normalized[(index - shift) % len(normalized)]
        for index in range(len(normalized))
    )

rotate_right_bits

rotate_right_bits(bits: Iterable[Any], amount: int) -> tuple

Rotate toward the LSB by a public amount (little-endian bit lists).

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bits to rotate.	required
amount	int	The encrypted integer amount to be processed.	required

Returns:

Name	Type	Description
tuple	tuple	The rotated bits.

Example

from concrete_fhe_toolkit.math.bits import rotate_right_bits

print(rotate_right_bits([0, 0, 1], amount=1))  # (0, 1, 0)

Source code in src/concrete_fhe_toolkit/math/bits.py

def rotate_right_bits(bits: Iterable[Any], amount: int) -> tuple:
    """Rotate toward the LSB by a public amount (little-endian bit lists).

    Args:
        bits (Iterable[Any]): The bits to rotate.
        amount (int): The encrypted integer amount to be processed.

    Returns:
        tuple: The rotated bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import rotate_right_bits

        print(rotate_right_bits([0, 0, 1], amount=1))  # (0, 1, 0)
        ```
    """
    normalized = tuple(bits)
    if not normalized:
        raise ValueError("bits must contain at least one bit")
    shift = validate_integer("amount", amount, minimum=0) % len(normalized)
    return tuple(
        normalized[(index + shift) % len(normalized)]
        for index in range(len(normalized))
    )

popcount_bits

popcount_bits(bits: Iterable[Any]) -> Any

Return the number of set bits as an integer expression (tournament sum).

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bit list.	required

Returns:

Name	Type	Description
Any	Any	The number of set bits.

Example

from concrete_fhe_toolkit.math.bits import popcount_bits

print(popcount_bits([1, 0, 1]))  # 2

Source code in src/concrete_fhe_toolkit/math/bits.py

def popcount_bits(bits: Iterable[Any]) -> Any:
    """Return the number of set bits as an integer expression (tournament sum).

    Args:
        bits (Iterable[Any]): The bit list.

    Returns:
        Any: The number of set bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import popcount_bits

        print(popcount_bits([1, 0, 1]))  # 2
        ```
    """
    layer = list(bits)
    if not layer:
        raise ValueError("bits must contain at least one bit")
    while len(layer) > 1:
        next_layer = []
        for index in range(0, len(layer) - 1, 2):
            next_layer.append(layer[index] + layer[index + 1])
        if len(layer) % 2 == 1:
            next_layer.append(layer[-1])
        layer = next_layer
    return layer[0]

parity_bits

parity_bits(bits: Iterable[Any]) -> Any

Return the XOR-parity (1 when an odd number of bits are set).

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bit list.	required

Returns:

Name	Type	Description
Any	Any	The parity bit.

Example

from concrete_fhe_toolkit.math.bits import parity_bits

print(parity_bits([1, 1, 1]))  # 1

Source code in src/concrete_fhe_toolkit/math/bits.py

def parity_bits(bits: Iterable[Any]) -> Any:
    """Return the XOR-parity (1 when an odd number of bits are set).

    Args:
        bits (Iterable[Any]): The bit list.

    Returns:
        Any: The parity bit.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import parity_bits

        print(parity_bits([1, 1, 1]))  # 1
        ```
    """
    return bit_xor_many(bits)

bit_length_bits

bit_length_bits(bits: Iterable[Any]) -> Any

Return the bit length (index of the highest set bit plus one, 0 for zero).

Parameters:

Name	Type	Description	Default
bits	Iterable[Any]	The bit list.	required

Returns:

Name	Type	Description
Any	Any	The bit length.

Example

from concrete_fhe_toolkit.math.bits import bit_length_bits

print(bit_length_bits([1, 0, 1, 0]))  # 3

Source code in src/concrete_fhe_toolkit/math/bits.py

def bit_length_bits(bits: Iterable[Any]) -> Any:
    """Return the bit length (index of the highest set bit plus one, 0 for zero).

    Args:
        bits (Iterable[Any]): The bit list.

    Returns:
        Any: The bit length.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import bit_length_bits

        print(bit_length_bits([1, 0, 1, 0]))  # 3
        ```
    """
    normalized = tuple(bits)
    if not normalized:
        raise ValueError("bits must contain at least one bit")
    running = normalized[-1]
    total: Any = running
    for index in range(len(normalized) - 2, -1, -1):
        running = bit_or(running, normalized[index])
        total = total + running
    return total

unsigned_compare_bits

unsigned_compare_bits(left_bits: Iterable[Any], right_bits: Iterable[Any]) -> tuple

Return (is_less, is_equal) bits for two little-endian unsigned bit lists.

Parameters:

Name	Type	Description	Default
left_bits	Iterable[Any]	The left bit list.	required
right_bits	Iterable[Any]	The right bit list.	required

Returns:

Name	Type	Description
tuple	tuple	A tuple containing the is_less and is_equal bits.

Example

from concrete_fhe_toolkit.math.bits import unsigned_compare_bits

print(unsigned_compare_bits([0, 1], [1, 1]))  # (1, 0)

Source code in src/concrete_fhe_toolkit/math/bits.py

def unsigned_compare_bits(
    left_bits: Iterable[Any],
    right_bits: Iterable[Any],
) -> tuple:
    """Return (is_less, is_equal) bits for two little-endian unsigned bit lists.

    Args:
        left_bits (Iterable[Any]): The left bit list.
        right_bits (Iterable[Any]): The right bit list.

    Returns:
        tuple: A tuple containing the is_less and is_equal bits.

    Example:
        ```python
        from concrete_fhe_toolkit.math.bits import unsigned_compare_bits

        print(unsigned_compare_bits([0, 1], [1, 1]))  # (1, 0)
        ```
    """
    left = tuple(left_bits)
    right = tuple(right_bits)
    width = max(len(left), len(right))
    if width == 0:
        raise ValueError("bit lists must contain at least one bit")
    padded_left = left + (0,) * (width - len(left))
    padded_right = right + (0,) * (width - len(right))

    is_less: Any = 0
    is_equal: Any = 1
    for index in range(width - 1, -1, -1):
        left_bit = padded_left[index]
        right_bit = padded_right[index]
        less_here = bit_and(bit_not(left_bit), right_bit)
        is_less = bit_or(is_less, bit_and(is_equal, less_here))
        is_equal = bit_and(is_equal, bit_not(bit_xor(left_bit, right_bit)))
    return is_less, is_equal