bit operation AND

Question

It is a leetcode problem. Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5]. My code is:

class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int axorb=0;
    for(auto i:nums) axorb=axorb^i;
    int differbit=(axorb&(axorb-1))^axorb;
    int group3=0, group5=0;
    for(auto i:nums)

if(differbit&i!=0) group5=group5^i;

        else group3=group3^i;
        return vector<int>{group3,group5};

}
};

submission result is wrong answer.

Input:[0,0,1,2]
Output:[3,0]
Expected:[1,2]

But if I just change highlighted part to

if(differbit&i) group5=group5^i;

it is accepted. I spent a lot of time thinking about but still have no idea. Maybe some type conversion happened? Thanks

score 6 · Accepted Answer · edited Jun 20 '20 at 09:12

This has to do with operator precedence.
Because in early C the && and || operators were added late it was given a very low priority so it wouldn't break legacy programs.

This Stack overflow Question has a very good answer as to why:

From this forum: http://bytes.com/topic/c/answers/167377-operator-precedence

The && and || operators were added later for their "short-circuiting" behavior. Dennis Ritchie admits in retrospect that the precedence of the bitwise operators should have been changed when the logical operators were added. But with several hundred kilobytes of C source code in existence at that point and an installed base of three computers, Dennis thought it would be too big of a change in the C language...

Here is A Table showing operator precedence.
Showing != at a higher priority than &.

As you can see bitwise & is lower than != on the table, so what your code is doing is the following:

if ( differbit & (i!=0) )

instead of what I assume you meant to do:

if ( (differbit & i) != 0 )

bit operation AND

1 Answers1

Linked