Introduction to Bitwise Tries
Get an introduction to the use of bitwise tries for solving XOR-related problems.
Bits
A bit (binary digit) is the smallest data unit that can be processed or stored by a computer. A bit is analogical to entities that can be in one of two possible states. Examples are a light switch which can be either on or off. Other examples represent the state as yes/no, on/off, or true/false.
Operations on bits
Bitwise operations function on the individual bits. These operations are fast and optimize the time complexity. Details of the most commonly used bit operators are described below.
NOT ( ~ )
Bitwise NOT is an unary operator. It converts the bit to its opposite bit. If the bit is 0, it’s converted to 1 and vice versa. It calculates the complement of a number. For example:
~ ~
AND ( & )
This operation can be performed on two equal-length bit patterns. If both the bits in the concerned position of the bit patterns are equal to 1, the bit in the output pattern is set to 1; otherwise, it’s set to 0. For example:
& &
OR ( | )
This operation is performed on two equal-length bit patterns, similar to bitwise AND. If both bits in the concerned position of the input bit patterns are 0, the bit in the resulting pattern is set to 0; otherwise, it’s set to 1. For example:
...