CODEWITHSUNDEEP
bitwise-operatorsbit-shift
bespectacled
bespectacled

Reputation: 2901

Bit shift operators

I came across such a programming interview question. But it is not obvious to me how you know bit shift can be used here. Someone kindly explain. Thanks.

An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers. Find which elements of first array are present in the second array. (If you are using extra memory, think of minimizing that still, using bitwise operators)

I would like to know what in the real world the bitshift operators mean. And how to identify the problems that require a bitshift approach.

Thanks Sanjay

Upvotes: 3

Views: 1927

Answers (2)

Tony Delroy
Tony Delroy

Reputation: 106096

It's a very easy interview question really. Because you know there's at most 1025 distinct integers in the first set, you can use that number of bits to represent whether each of those numbers is found or not in input sets. So, if you want the answer to print each distinct number exactly once, the logic is:

  • zero all the 1025 bits in bitset A
  • for each number in the first set, set the corresponding bit in A
  • zero all the 1025 bits in bitset B
  • for each number int he second set, set the corresponding bit in B
  • for i from 0 to 1024: if that bit is set in both A and B, output i as part of your answer

Now, to create a bitset of 1025 bits might not be supported directly by your language, so what you sometimes have to do is use an array of bytes, each of which has 8 bits. Then, say you want to set bit "k", you'll find the byte at index k / 8, then set the bit at position k % 8. To do the latter, you have to convert from a bit position (0 through 7) to a bit value (bit 0 represents value 1, bit 1 value 2, bit 2 value 4... bit 7 value 128 - all the powers of two). To get these values, you take the number 1 and bitshift it left by the "bit position". So, 1 << 0 is still 1, while 1 << 7 is 128. You can then:

  • ask if a byte has that bit on by ANDing the shifted value with the byte's value and seeing if you get a non-0 result - for example, in C and C++: if (array[k / 8] & (1 << (k % 8))) ...it's on...
  • record a 1 at a particular bit position in a byte by ORing the value with the byte - in C and C++: array[k / 8] |= (1 << (k % 8));

There are more efficient ways to do this if there happens to be a lot less than 1025 values in either set, but this is a good general solution.

Upvotes: 5

Gayan Hewa
Gayan Hewa

Reputation: 2397

Bitshift operators work like this. Imagine you have an integer value X. This X will be represented in Binary form , which is 1 and 0's. After words according to the shift operator. Number of positions will be moved.

Visit this link http://www.php.net/manual/en/language.operators.bitwise.php they have some examples on how this shift operators work.

Upvotes: 1

Related Questions