[02 Aug 2020] Find position of the only set bit

 #include <bits/stdc++.h>

using namespace std;




// A utility function to check whether n is a power of 2 or not.

// See http://goo.gl/17Arj

int isPowerOfTwo(unsigned n)

{

    return n && (!(n & (n - 1)));

}

  

// Returns position of the only set bit in 'n'

int findPosition(unsigned n)

{

    if (!isPowerOfTwo(n))

        return -1;

  

    unsigned i = 1, pos = 1;

  

    // Iterate through bits of n till we find a set bit

    // i&n will be non-zero only when 'i' and 'n' have a set bit

    // at same position

    while (!(i & n)) {

        // Unset current bit and set the next bit in 'i'

        i = i << 1;

  

        // increment position

        ++pos;

    }

  

    return pos;

}

  

// Driver program to test above function

int main(void)

{

    int n = 16;

    int pos = findPosition(n);

    (pos == -1) ? cout << "n = " << n << ", Invalid number" << endl : cout << "n = " << n << ", Position " << pos << endl;

  

    n = 12;

    pos = findPosition(n);

    (pos == -1) ? cout << "n = " << n << ", Invalid number" << endl : cout << "n = " << n << ", Position " << pos << endl;

  

    n = 128;

    pos = findPosition(n);

    (pos == -1) ? cout << "n = " << n << ", Invalid number" << endl : cout << "n = " << n << ", Position " << pos << endl;

  

    return 0;

}




[2] Count total set bits in all numbers from 1 to n

Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.

Examples:

Input: n = 3
Output:  4

Input: n = 6
Output: 9

Input: n = 7
Output: 12

Input: n = 8
Output: 13

// A simple program to count set bits

// in all numbers from 1 to n.

#include <stdio.h>

  

// A utility function to count set bits

// in a number x

unsigned int countSetBitsUtil(unsigned int x);

  

// Returns count of set bits present in all

// numbers from 1 to n

unsigned int countSetBits(unsigned int n)

{

    int bitCount = 0; // initialize the result

  

    for (int i = 1; i <= n; i++)

        bitCount += countSetBitsUtil(i);

  

    return bitCount;

}

  

// A utility function to count set bits 

// in a number x

unsigned int countSetBitsUtil(unsigned int x)

{

    if (x <= 0)

        return 0;

    return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2);

}

  

// Driver program to test above functions

int main()

{

    int n = 4;

    printf("Total set bit count is %d", countSetBits(n));

    return 0;

}




Total set bit count is 5

Time Complexity: O(nLogn)