Creating Left most unset bit to set

Question is

and my solution is

What I think is

  1. calculate total number of bits;
  2. creater number by 1<<(total bits)
    3.run a loop and take and with the given number
    (i) if(number & with created number in step 2 is zero it means we find left unset bit then take OR of both and break;
    (ii) Else Right shift the created number and get in Loop

Why there is TLE.
Edit 1. I know this is long approach but it is what that I think… Please Help

\bullet line 17: should be

s != 0

instead of

k != 0

[as k is not the one decreasing]

\bullet line 19: should be

if((((k&s) >> --count) & 1)==0)

instead of

if(k&s==0)

[as you are trying to isolate and find whether 1 particular bit is set / unset]

Here I’ve corrected the code and it works just fine and dandy. :slightly_smiling_face:

1 Like

Thank you so much …

1 Like

You’re welcome :slightly_smiling_face:

1 Like

But what is need of line 19 removing extra things that is --count & 1 code works fine

Let me explain this to you using an example. I’ll be considering nybbles of data.
Let us assume k = 1011 and s = 1111 in binary. Notice the bit position 2:

bit positions:
3|2|1|0

1|0|1|1
1|1|1|1
\&
\rule{1.5cm}{0.4pt}
1|0|1|1 is != 0

Your code stopped checking here.
But, I added the following to isolate bit position 2:

1|0|1|1 >> 2 = 0|0|1|0
and,

0|0|1|0
0|0|0|1
\&
\rule{1.5cm}{0.4pt}
0|0|0|0 is = 0

That’s why we need to shift and then logically and it with 1 for isolating a single bit. Do tell me if you still have anymore doubts. :slightly_smiling_face:

1 Like

When k is 1011
Then s is why 1111 it is 1000 because I shift s <<(count-1)

I assumed two arbitrary numbers for k and s in order to explain the bit isolation procedure.

Bur s is not arbitrary in my solution I createD s by shifting left

Then, you may consider s = 0100 to be a valid intermediate value though it starts off with s = 1000, which I didn’t cover as it would give no interesting result and both your and my code would work in that case.

1 Like

Yes when s become 0100 after shifting loops breaks because I find answer

1 Like

Corrrrrect!!! :smile:

1 Like

Thank you so much for giving your precious time

1 Like

No problem buddy. :slightly_smiling_face:

1 Like