CODEWITHSUNDEEP
c
lee chong wei
lee chong wei

Reputation: 53

bitwise operation for c confusion

Assuming that x is a positive integer, the following function returns 1 if x is a certain type of values or it returns 0 otherwise.

int mystery(int x) {
    return !((x-1) & x);
}

What does mystery(20) return?

May I ask how do we approach this type of qn ? My idea is to express x in binary and do bitwise operation with it. Do correct me if I am wrong thanks !

Upvotes: 0

Views: 67

Answers (1)

Jim Stockwell
Jim Stockwell

Reputation: 186

Let's work from the outside in.

!(expression)

you will get a 0 if expression is true, that is, not zero, and you will get a 1 if expression is false, that is, zero.

So when will expression be non-zero, giving a zero as a result? Whenever (x-1) has some bits in common with x.

What are examples?

  • 0 - 1 = 0xfff... & 0, no bits in common, returns 1
  • 1 - 1 = 0 & 1, no bits in common, returns 1
  • 2 - 1 = 1 & 2, no bits in common, returns 1
  • 3 - 1 = 2 & 3, bits in common, returns 0
  • 4 - 1 = 3 & 4, no bits in common, returns 1
  • 5 - 1 = 4 & 5, bits in common, returns 0
  • 6 - 1 = 5 & 6, bits in common, returns 0
  • 7 - 1 = 6 & 7, bits in common, returns 0
  • 8 - 1 = 7 & 8, no bits in common, returns 1

It looks to me like we can say it returns 1 when the binary representation has exactly zero or one bits turned on in it.

0 or 1 or 10 or 100

Upvotes: 1

Related Questions