c++bit-manipulationbitwise-operators

Bit operation AND

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 the 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 I still don't have any idea. Maybe some type conversion happened?

Solution

  • This has to do with operator precedence.

    Because in early C, the && and || operators were added late, and 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.

    Enter image description here

    Showing != at a higher priority than &.

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

    if ( differbit & (i!=0) )

    instead of what I assume you meant to do:

    if ( (differbit & i) != 0 )