Bit extraction
Some applications require directly manipulating bits of integers. Concrete provides a bit extraction operation for such applications.
Bit extraction is capable of extracting a slice of bits from an integer. Index 0 corresponds to the lowest significant bit. The cost of this operation is proportional to the highest significant bit index.
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.
Slices can be used for indexing fhe.bits(value)
as well.
Even slices with negative steps are supported!
Signed integers are supported as well.
Lastly, here is a practical use case of bit extraction.
prints
Limitations
Bits cannot be extracted using a negative index.
Which means
fhe.bits(x)[-1]
orfhe.bits(x)[-4:-1]
is not supported for example.The reason for this is that we don't know in advance (i.e., before inputset evaluation) how many bits
x
has.For example, let's say you have
x == 10 == 0b_000...0001010
, and you want to dofhe.bits(x)[-1]
. If the value is 4-bits (i.e.,0b_1010
), the result needs to be1
, but if it's 6-bits (i.e.,0b_001010
), the result needs to be0
. Since we don't know the bit-width ofx
before inputset evaluation, we cannot calculatefhe.bits(x)[-1]
.
When extracting bits using slices in reverse order (i.e., step < 0), the start bit needs to be provided explicitly.
Which means
fhe.bits(x)[::-1]
orfhe.bits(x)[:2:-1]
is not supported for example.The reason is the same as above.
When extracting bits of signed values using slices, the stop bit needs to be provided explicitly.
Which means
fhe.bits(x)[1:]
orfhe.bits(x)[1::2]
is not supported for example.The reason is similar to above.
To explain a bit more, signed integers use two's complement representation. In this representation, negative values have their most significant bits set to 1 (e.g.,
-1 == 0b_11111
,-2 == 0b_11110
,-3 == 0b_11101
). Extracting bits always returns a positive value (e.g.,fhe.bits(-1)[1:3] == 0b_11 == 3
) This means if you were to dofhe.bits(x)[1:]
wherex == -1
, ifx
is 4 bits, the result would be0b_111 == 7
, but ifx
is 5 bits the result would be0b_1111 == 15
. Since we don't know the bit-width ofx
before inputset evaluation, we cannot calculatefhe.bits(x)[1:]
.
Bits of floats cannot be extracted.
Floats are partially supported but extracting their bits is not supported at all.
Performance Considerations
A Chain of Individual Bit Extractions
Key Concept: 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 extractingfhe.bits(x)[0]
.Extracting
fhe.bits(x)[4]
takes around five times more wall clock time thanfhe.bits(x)[0]
.The cost of extracting
fhe.bits(x)[0:5]
is almost the same as that offhe.bits(x)[5]
.
Reuse of Intermediate Extracted Bits
Key Concept: 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 inputx
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.
Last updated