3

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

Improve this question
1
  • 1
    The question referred to "bitwise" operators, not "bit shift" operators. This is a more general term (see Wikipedia). Commented Jun 13, 2011 at 12:09

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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.

Improve this answer

2 Comments

He isn't asking about bitwise operators in general, he is asking about their real-world applications and their relevance to this question.
Yeah but , to understand the underling concept he first needs to know how bitwise operators work.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.