Count numbers up to N having Kth bit set | C ++ program for above approach ; Function to return the count of number of 1 's at ith bit in a range [1, n - 1] ; Store count till nearest power of 2 less than N ; If K - th bit is set in N ; Add to result the nearest power of 2 less than N ; Return result ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long getcount ( long long n , int k ) { long long res = ( n >> ( k + 1 ) ) << k ; if ( ( n >> k ) & 1 ) res += n & ( ( 1ll << k ) - 1 ) ; return res ; } int main ( ) { long long int N = 14 ; int K = 2 ; cout << getcount ( N + 1 , K ) << endl ; return 0 ; }