AND operator
Lesson 5 of 17 in Coddy's Bit Manipulation course.
AND ( &) operator
Bitwise AND is a binary operator that operates on two equal-length bit patterns. If both bits in the compared position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0. '&' symbol represents AND operator.
The table below shows AND operation on two bits.
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| x & y | 0 | 0 | 0 | 1 |
Let's take an example and understand AND operation better.
In the example above we have done AND operation on (11)10 and (6)10 which resulted in (2)10. We simply wrote these numbers in there binary form and compared the two bits, if there was any zero present we simply included 0 in the resulting bit pattern.
Usage:
int a = 1;
int b = 0;
>> a & b
OUTPUT: 0
Challenge
EasyTim discovers some stones in a cave while trekking with numbers written on them. All the stones are placed in a sequence. Near those stones he discovers a mystical diary that says these stones are magical and has certain conditions mentioned in order for them to perform magic. Which are -
- The magic stones appear in a group of 2.
- The stones are supposed to be selected in a contiguous manner and the group must not include a stone selected previously.
- The third condition was not readable. So, Tim experiments with the stones and he finds out that magic is only performed by the stones when AND operation applied on the numbers appearing in the group yields a zero.
Find out the group that performed magic and output the number written on first stone of the group.
For instance let's say, the stones he found were placed as-
[ 5 , 2 , 3 , 6 , 1 , 9 ]So, firstly Tim divides these stones in contiguous non-repeating groups of 2. { (5,2) , (3,6) , (1,9) }
Then performs AND ( & ) operation over these groups and finds out that it is the first group which will perform magic. 5=> (101)2 and 2=>(010)2. Only this group out of the three groups will give zero on performing AND operation on them.
And the output we will get is 5 as we need the number on the first stone of the group in order to identify the group.
Also note that all the sequences contain even number of elements and out of the given sequences there always exists one and only one group which will perform magic. Your challenge is to complete the function "MagicStones" to find out the magical group Tim discovered.
Try it yourself
#include <iostream>
#include <vector>
using namespace std;
int MagicStones(vector<int> stone_sequence) {
// Write code here
}