BIT predicate

In mathematics and computer science, the BIT predicate or Ackermann coding, sometimes written BIT(i, j), is a predicate which tests whether the jth bit of the number i is 1, when i is written in binary.

The BIT predicate was first introduced as the encoding of hereditarily finite sets as natural numbers by Wilhelm Ackermann in his 1937 paper (The Consistency of General Set Theory).

Each natural number encodes a finite set and each finite set is represented by a natural number. This mapping uses the binary numeral system. If the number n encodes a finite set A and the ith binary digit of n is 1, then the set encoded by i is an element of A.

The Ackermann coding is a primitive recursive function.

In programming languages such as C, C++, Java, or Python that provide a right shift operator >> and a bitwise Boolean and operator &, the BIT predicate BIT(i, j) can be implemented by the expression (i>>j)&1. Here the bits of i are numbered from the low order bits to high order bits in the binary representation of i, with the ones bit being numbered as bit 0.

In the mathematical study of computer security, the private information retrieval problem can be modeled as one in which a client, communicating with a collection of servers that store a binary number i, wishes to determine the result of a BIT predicate BIT(i, j) without divulging the value of j to the servers. Chor et al. (1998) describe a method for replicating i across two servers in such a way that the client can solve the private information retrieval problem using a substantially smaller amount of communication than would be necessary to recover the complete value of i.

...
Wikipedia