abhinav700's blog

Have some doubts in the operation (n<<32) [Bitwise Manipulation]
By abhinav700, history, 2 years ago, In English

I was doing a question on leetcode and the part of it's solution required to find the rightmost set bit of an integer(it can also be negative).It is given that integer is a 32 bit number in constraints.

While finding out the position of right most bit using below function

int findPos(int allXor){
        int flag=1;
        int i;
        for( i=0;i<=32;i++)
            if((1<<i) & allXor )
                break;
        return i;
    }

i am unable to understand that how 1<<32 is going to work. It is because we are given a 32 bit number and 1<<32 would represent the integer which has it's 33rd bit set right? when i use i<=31 in this question i get the wrong answer.

Can someone pls explain what is happening here?

QUESTION LINK: https://leetcode.com/problems/single-number-iii/

FULL CODE:

class Solution {
public:
    int findPos(int allXor){
        int flag=1;
        int i;
        for( i=0;i<=32;i++)
            if((1<<i) & allXor )
                break;
        return i;
    }
    
    vector<int> singleNumber(vector<int>& nums) {
        if(nums.size()==2)
            return nums;
        vector<int> ans;
        int allXor=0;
        for(auto it: nums)
            allXor^=it;
        int bitPos=findPos(allXor);
        // cout<<allXor<<" "<<bitPos<<endl;
        vector<int> part1,part2;
        
        for(auto it: nums){
            if((1<<bitPos)&it)
                part1.push_back(it);
            else
                part2.push_back(it);
        }
        
        int element1=0,element2=0;
        for(auto it : part1)
        {
              element1^=it;
              cout<<it<<" ";
        }
        cout<<endl;
        for(auto it : part2)
        {
               element2^=it;
                cout<<it<<" ";
        }
        return {element1,element2};
    }
};
  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

while 1<<32 itself is undefined behaviour, it generally works as 1<<0 in many compilers. in this example the for statement loops until $$$32$$$ simply to handle the case of $$$0$$$, where there are no bits and we can effectively say the number has $$$32$$$ trailing zeroes.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    while 1<<32 itself is undefined behaviour

    You shouldn't be trying to justify using UB at any point, since it is literally undefined. If UB is present, the compiler can even optimize away your whole program, and that is one of the more tame things it can do (GCC sometimes does that when you don't return something from a function that was supposed to return something, like an integer). Even if all UBs are not created equal, you never know what UB an optimizing compiler can take advantage of.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I wasn't trying to justify using UB, just meant to explain what does happen in this specific case. We need to avoid any UB if possible, but in this case it already did happen in the given code (this being said, it's not quite easy to eliminate all UB in any given code, there are too many kinds of UB to consider)

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I assume WA has nothing to do with that loop. Moreover I could recommend you to check out some resources to see many ways how you can find the rightmost set bit, might be interesting on this occasion.

→ Reply