[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)








































































Comments

Post a Comment

Popular posts from this blog

Typical Programs in C/C++

  Sum of two large numbers Difficulty Level :   Medium   Last Updated :  04 Jun, 2019 Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers. Examples: Input : str1 = "3333311111111111", str2 = "44422222221111" Output : 3377733333332222 Input : str1 = "7777555511111111", str2 = "3332222221111" Output : 7780887733332222 The idea is based on school mathematics. We traverse both strings from end, one by one add digits and keep track of carry. To simplify the process, we do following: 1) Reverse both strings. 2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10. 3) Finally reverse the result. // C++ program to find sum of two large numbers. #include<bits/stdc++.h> using namespace std;     // Function for finding sum of la...
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more
Image
  C Program to Check if a Given String is Palindrome // A function to check if a string str is palindrome void isPalindrome( char str[]) {      // Start from leftmost and rightmost corners of str      int l = 0;      int h = strlen (str) - 1;          // Keep comparing characters while they are same      while (h > l)      {          if (str[l++] != str[h--])          {              printf ( "%s is Not Palindrome" , str);              return ;          }      }      printf ( "%s is palindrome" , str); }     // Driver program to test above function int main() {...
Read more