Prime Check With Bit Manipulation

MediumPython

Problem

Amazon Lab126 firmware validation may need to inspect an integer configuration value and transform selected flag bits. Given a non-negative integer n and two bit indices, determine whether n is prime and swap the bits at those positions using bit manipulation.

Bit index 0 is the least significant bit. The swap must work even when one position currently contains 0. Return both results in a dictionary with keys is_prime and swapped.

Formal Specification

Implement prime_and_swap(n, i, j):

Input: n, a non-negative integer; i and j, zero-based bit indices.
Output: A dictionary containing is_prime, a Boolean indicating whether the original n is prime, and swapped, the integer after exchanging bits i and j.
The primality result must be computed from the original value, before the swap.
If the two selected bits are equal, the integer remains unchanged.

Constraints

0 <= n <= 10^9
0 <= i, j <= 30
i and j may be equal
The primality result refers to the original value of n
Do not convert n to a string for the bit swap

Function Signature

def prime_and_swap(n, i, j):

Bit index 0 is the least significant bit. The swap must work even when one position currently contains 0. Return both results in a dictionary with keys is_prime and swapped.

Formal Specification

Implement prime_and_swap(n, i, j):

Input: n, a non-negative integer; i and j, zero-based bit indices.
Output: A dictionary containing is_prime, a Boolean indicating whether the original n is prime, and swapped, the integer after exchanging bits i and j.
The primality result must be computed from the original value, before the swap.
If the two selected bits are equal, the integer remains unchanged.