Bit Manipulation and Mathematical Reasoning Flashcards
6 cards from real CodeSignal Technical Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Bit Manipulation and Mathematical Reasoning flashcards as text
What technique computes a^b mod m in O(log b) time?
Answer: Binary exponentiation (fast power)
Binary exponentiation squares the base and halves the exponent at each step, reducing the number of multiplications to O(log b).
Which expression correctly checks if integer n is odd using bit manipulation?
Answer: (n & 1) == 1
The least significant bit is 1 for odd numbers and 0 for even numbers, so ANDing with 1 tests parity.
What does `n | (n-1)` do to integer n?
Answer: Sets all bits from position 0 up through the lowest set bit of n
n-1 flips the lowest set bit and sets all bits below it, so OR-ing with n fills in all lower bit positions.
What property of modular arithmetic allows `(a * b) mod m` to equal `((a mod m) * (b mod m)) mod m`?
Answer: Distributivity of modulo over multiplication
Modulo distributes over multiplication, which lets you reduce large operands before multiplying to avoid overflow.
What is the time complexity of Brian Kernighan's algorithm for counting set bits?
Answer: O(number of set bits)
Each iteration of the loop removes one set bit using n &= (n-1), so the loop runs once per set bit.
What is the result of `n ^ (n-1)` when n = 8 (binary 1000)?
Answer: 15
8 is 1000 and 7 (8-1) is 0111; XOR gives 1111, which equals 15 in decimal.