Pages

Bit check

Given an unsigned int and two numbers representing the one-based index of bits (from the least significative one) in that word, write a function that returns true if those bits have the same value.

This problem is based on the CodeEval Bit Positions challenge.

A test case (C++ for GoogleTest) should be enough to clarify the requirements:
TEST(BiPo, CaseGiven)
{
  EXPECT_TRUE(solution(86, 2, 3)); // 1
  EXPECT_FALSE(solution(125, 1, 2)); // 2
}
1. 86 base ten is 1010110 base two. Its second and third bit from left are both set to 1. We expect our function to return true.
2. 125 base ten is 1111101 base two. Its first bit is 1 and the second is 0. Therefore the function should return false.

Here is my C++ implementation:
bool solution(unsigned word, int p1, int p2)
{
  bool one = word & static_cast<int>(std::pow(2, p1-1)); // 1
  bool two = word & static_cast<int>(std::pow(2, p2-1));

  return !((one) ^ (two)); // 2
}
1. I convert the passed index in the associated binary value. If I had 3 in input, this mean that I want to check the third bit, whose binary value is 100, a decimal four. Then I apply a bitwise-and (the operator &) to the input word and the converted bit value. Its result will be true if the input word value has that bit up.
2. I want to return true if the selected bits (one and two) have the same value. To do that I apply a bitwise-exclusive-or (operator ^) to the bit flags. It would return true if the two flags are mutually exclusive (if one is true, the other is false), that is the exact opposite of what I want the function return. So it is just a matter of negating it (operator !).

The original CodeEval problem asks to output a string ("false" or "true") accordingly to the boolean value we get. This could be easily achieved through the ios boolalpha manipulator:
std::cout << std::boolalpha << solution(n, p1, p2) << std::endl;

No comments:

Post a Comment