4
$\begingroup$

I have an array of numbers, say [1,2,3,4,5,6], I want to find the element in the array which is equal to the bitwise OR of remaining elements.

Currently, my approach is to find bitwise OR of all the numbers in the array as follows, i.e., $$X = 1 | 2|3|4|5|6$$ Then I am trying to just filter out one a number at a time from X and check if they are equal. For example, if I am checking for number 4, I want something like this - $$(\{X-4\} == 4)?$$ I can easily do this in case of XOR. But not sure how to achieve $\{X-4\}$ in case of bitwise OR?

Improve this question
$\endgroup$
7
$\begingroup$

You are making things far too hard. Rather than successively taking out one element at a time, and doing a check, you can simply take a one-time bitwise OR of all elements: If there is an element that is the result of the bitwise OR on all others, then that element will also be the bitwise OR of all elements, including itself!

Here is why:

Assuming that there is indeed one such element, then for any bit position it will be true that the bit of the element you are looking for is a $1$ if and only if at least one of the bits of the other elements is a $1$.

So, it is impossible to have that bit being a $1$ when the corresponding bits of the other numbers are all $0$, and it is also impossible for that bit being a $0$ when there is at least one corresponding bit that's a $1$.

That means that if we OR the value of the bit of the element we are looking for with all the corresponding bits from all the other elements, we get the value of the first bit.

Therefore, the value of that bit equals the value of the OR of all the bits for that position, and thus we can simply take the OR of all bits for that position to find the value of the bit we want.

In other words, you can simply take the bitwise OR for all elements, and then see which of the elements equals the result of that: that's the element you are looking for.

So notice that with numbers $1$ through $6$ there is no element that is the result of the bitwise OR on all other elements, because for every position there are at least two $1$'s, and hence the bitwise or of any fice elements will give you $111$, i.e. $7$.

However, if you take numbers $1$ through $7$, then not only is $7$ the bitwise OR of $1$ through $6$, but also of $1$ through $7$, and as I just explained, it has to be that way, again assuming there is such an element in the first place.

Improve this answer
$\endgroup$
  • $\begingroup$ How did you know that the needed element is presumed to necessarily exist? I don't see that in the question. $\endgroup$ – Serge Seredenko Mar 18 '18 at 16:51
  • $\begingroup$ It doesn't have to exist; but if it did exist, it would be the number described here, so once the relevant number has been found with this procedure, it can be quickly tested. (And note that unlike the XOR case, there can be only one number that meets the criteria, because of the argument that this answer gives.) $\endgroup$ – Steven Stadnicki Mar 18 '18 at 16:53
  • $\begingroup$ @SergeSeredenko The OP writes "I want to find the element in the array which is equal to the bitwise OR of remaining elements." ... I interpret that as saying that there is one, otherwise you would think the OP would have written "I want to see if there is an element which ...". Anyway, several times in my answer I make it quite clear that the method described presumes that is indeed such an element. In the first paragraph I write: "If there is an element that is the result of the bitwise OR on all others, ..". The second paragraph: "Assuming that there is indeed one such element, .." $\endgroup$ – Bram28 Mar 18 '18 at 17:14
  • $\begingroup$ @Bram28 I see that you wrote that, and I was just wondering why. Never mind, Steven already explained the end of procedure. $\endgroup$ – Serge Seredenko Mar 18 '18 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.