aboutsummaryrefslogtreecommitdiff
path: root/find_kth_bit_nth_bin_str.c
blob: c3fa6a56454005d137732251fb83c326d2657e2c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 1545. Find Kth Bit in Nth Binary String
#include "leetcode.h"

/*
 * given two positive integers 'n' and 'k', the binary string 's_n' is formed as
 * follows: 's_1 = 0', 's_i = s_i - 1 + "1" + reverse(invert(s_i - 1))' for 'i >
 * 1'. where '+' denotes the concatenation operation, 'reverse(x)' returns the
 * reversed string 'x', and 'invert(x)' inverts all teh bits in 'x'. return the
 * k'th bit in 's_n'. it is guaranteed that 'k' is valid for the given 'n'.
 */

int max_bit(int n) {
  while ((n & (n - 1)))
    n &= n - 1;
  return n;
}

char findKthBit(int n, int k) {
  int inv = 0;
  while (k & (k - 1)) {
    k = -k & (max_bit(k) - 1);
    inv ^= 1;
  }
  return ((k > 1) ^ inv) + '0';
}

int main() {
  printf("%c\n", findKthBit(3, 1));  // expect: 0
  printf("%c\n", findKthBit(4, 11)); // expect: 1
}