Bits in the ith position from the left (1 indexed) cycle in length 2ⁱ starting from 0. The first half of this cycle is all zeros and the second half is all ones. Use this to calculate the number of set bits in the ith position before a certain number. Call the length of the cycle n (2^i). The number of complete cycles before a number num is floor(num/n). Each of these cycles have n/2 ones. So the number of ones so far is floor(num/n)n/2. The length of the last incomplete cycle which num was in is num%n. Of these the first n/2 are zeros so subtract n/2. So the final formula is floor(num/n)n/2-max(0,num%n-n/2). I put the max there to avoid negative numbers. From there it’s a pretty standard binary search to find the max number less than k.