Bit Flips to Match an OR

Medium

You get three positive integers x, y and target. In one operation you may flip a single bit in the binary form of x or y, turning a 0 into a 1 or a 1 into a 0. target itself stays as it is. Return the smallest number of operations needed to make the bitwise OR x | y equal to target.

Example 1

x=3, y=12, target=9 → 2

x = 0011, y = 1100, target = 1001, and currently x | y = 1111. Clear bit 1 of x and bit 2 of y: 2 flips.

Example 2

x=6, y=6, target=1 → 5

Bits 1 and 2 are set in both numbers, which takes 4 flips, plus one more to set bit 0: 5 in total.

Example 3

x=5, y=2, target=7 → 0

Constraints

1 ≤ x, y, target ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation

Similar problems

Division Without Dividing Medium Every Topping Combo Medium Mirrored One-Bit Codes Medium All Distinct Card Hands Medium The Odd One Among Triples Medium

Input

x=3, y=12, target=9

Expected

Run checks the first 3 tests in your browser. Submit checks all 78 tests on the server, hidden ones included.