# Bit extraction This document provides an overview of the bit extraction feature in **Concrete**, including usage examples, limitations, and performance considerations. ## Overview Bit extraction could be useful in some applications that require directly manipulating bits of integers. Bit extraction allows you to extract a specific slice of bits from an integer, where index 0 corresponds to the least significant bit (LSB). The cost of this operation increases with the index of the highest significant bit you wish to extract. {% hint style="warning" %} Bit extraction only works in the `Native` encoding, which is usually selected when all table lookups in the circuit are less than or equal to 8 bits. {% endhint %} ## Extracting a specific bit ```python from concrete import fhe @fhe.compiler({"x": "encrypted"}) def f(x): return fhe.bits(x)[0], fhe.bits(x)[3] inputset = range(32) circuit = f.compile(inputset) assert circuit.encrypt_run_decrypt(0b_00000) == (0, 0) assert circuit.encrypt_run_decrypt(0b_00001) == (1, 0) assert circuit.encrypt_run_decrypt(0b_01100) == (0, 1) assert circuit.encrypt_run_decrypt(0b_01101) == (1, 1) ``` ## Extracting multiple bits with slices You can use slices for indexing `fhe.bits(value)` : ```python from concrete import fhe @fhe.compiler({"x": "encrypted"}) def f(x): return fhe.bits(x)[1:4] inputset = range(32) circuit = f.compile(inputset) assert circuit.encrypt_run_decrypt(0b_01101) == 0b_110 assert circuit.encrypt_run_decrypt(0b_01011) == 0b_101 ``` Bit extraction supports slices with negative steps: ```python from concrete import fhe @fhe.compiler({"x": "encrypted"}) def f(x): return fhe.bits(x)[3:0:-1] inputset = range(32) circuit = f.compile(inputset) assert circuit.encrypt_run_decrypt(0b_01101) == 0b_011 assert circuit.encrypt_run_decrypt(0b_01011) == 0b_101 ``` ## Bit extraction with signed integers Bit extraction supports signed integers: ```python from concrete import fhe @fhe.compiler({"x": "encrypted"}) def f(x): return fhe.bits(x)[1:3] inputset = range(-16, 16) circuit = f.compile(inputset) assert circuit.encrypt_run_decrypt(-14) == 0b_01 # -14 == 0b_10010 (in two's complement) assert circuit.encrypt_run_decrypt(-12) == 0b_10 # -12 == 0b_10100 (in two's complement) ``` ### Use case example Here's a practical example that uses bit extraction to determine if a number is even: ```python import numpy as np from concrete import fhe @fhe.compiler({"x": "encrypted"}) def is_even(x): return 1 - fhe.bits(x)[0] inputset = [ np.random.randint(-16, 16, size=(5,)) for _ in range(100) ] circuit = is_even.compile(inputset) sample = np.random.randint(-16, 16, size=(5,)) for value, value_is_even in zip(sample, circuit.encrypt_run_decrypt(sample)): print(f"{value} is {'even' if value_is_even else 'odd'}") ``` It prints: ``` 13 is odd 0 is even -15 is odd 2 is even -6 is even ``` ## Limitations * **Negative indexing is not supported:** Bits extraction using negative indices is not supported, such as `fhe.bits(x)[-1]`. * This is because the bit-width of `x` is unknown before inputset evaluation, making it impossible to determine the correct bit to extract. * **Reverse slicing requires explicit starting bit:** When extracting bits in reverse order (using a negative step), the start bit must be specified, for example, `fhe.bits(x)[::-1]` is not supported. * **Signed integer slicing requires explicit stopping bit**: For signed integers, when using slices, the stop bit must be explicitly provided, for example, `fhe.bits(x)[1:]` is not supported. * **Float bit extraction is not supported**: While Concrete supports floats to some extent, bit extraction is not possible on float types. ## Performance considerations ### A Chain of individual bit extractions Extracting a specific bit requires clearing all the preceding lower bits. This involves extracting these previous bits as intermediate values and then subtracting them from the input. **Implications:** * Bits are extracted sequentially, starting from the least significant bit to the more significant ones. The cost is proportional to the index of the highest extracted bit plus one. * No parallelization is possible. The computation time is proportional to the cost, independent of the number of CPUs. **Examples:** * Extracting `fhe.bits(x)[4]` is approximately five times costlier than extracting `fhe.bits(x)[0]`. * Extracting `fhe.bits(x)[4]` takes around five times more wall clock time than `fhe.bits(x)[0]`. * The cost of extracting `fhe.bits(x)[0:5]` is almost the same as that of `fhe.bits(x)[5]`. ### Reuse of Intermediate Extracted Bits Common sub-expression elimination is applied to intermediate extracted bits. **Implications:** * The overall cost for a series of `fhe.bits(x)[m:n]` calls on the same input `x` is almost equivalent to the cost of the single most computationally expensive extraction in the series, i.e. `fhe.bits(x)[n]`. * The order of extraction in that series does not affect the overall cost. **Example**: The combined operation `fhe.bit(x)[3] + fhe.bit(x)[2] + fhe.bit(x)[1]` has almost the same cost as `fhe.bits(x)[3]`. ### TLUs of 1b input precision Each extracted bit incurs a cost of approximately one TLU of 1-bit input precision. Therefore, `fhe.bits(x)[0]` is generally faster than any other TLU operation. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.zama.org/concrete/operations/other-operations/bit_extraction.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.