EPI Java 4.4 Find a closest integer with the same weight - Variant

#1

Does anyone know the solution for O(1) time and space on this question? I feel like the solution given on the book is optimal. Thanks in advance!

0 Likes
#2

Yeah check it out: 4.4 Closest isoweight bit string O(1) time and space variant + suggestion

0 Likes
#3

Thanks for the sharing, and the idea is basically to use bitwise operators to compute the answer.

0 Likes
#4

@Hitchcock, I arrived at this solution in C++

int f(int x) {
  int to_flip = x & ~(x-1);
  if (to_flip & 1) {
    to_flip = (~x & ~(~x-1));
  }
  int mask = (to_flip) | (to_flip >> 1);
  return x ^ mask;
}
0 Likes
#5

Hi all, I arrived at this solution:

if (x & 1) {
    return ((x ^ (x+1))  >> 2) | (x+1);
} else {
    return ~((x ^ (x-1)) >> 2) & (x-1);
}
0 Likes
#6

Hi @jopez can you explain the intuition behind your logic?

0 Likes