Mohsina_Shaikh's blog

Finding Rightmost Set Bit For an Number
By Mohsina_Shaikh, history, 2 years ago, In English

Is finding rightmost set bit by this approach wrong.

int ans=xorsum,int rightmost=0;
 while(ans){
            int mask=1<<i;
            if(ans&mask){
                break;
            }
            ans=ans>>1; 
            i++;
        }
   rightmost=1<<i;

My code gave WA for some test cases when I used this code snippet to find rightmost set bit.It worked when I removed this with rightmost=xorsum&(-xorsum) can anyone please why the above got snippet may not work.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Why are you both left shifting the mask AND right shifting the number in which you're searching? "ans = ans >> 1" is the problem here; delete it and you should have no more problems.

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

You should remove ans=ans>>1;, the i++ and 1<<i already move you to the left so there's no need to move ans to the right. if ans==48 you get 4 when the answer is 16

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

    also I think this causes the snippet to miss odd powers of two entirely.

    → Reply