Set all even bits of a number
Given a number, the task is to set all even bits of a number. Positions of bits are counted from LSB (least significant bit) to MSB (Most significant bit). The position of LSB is considered as 1.
Examples :
Input : 20 Output : 30 Binary representation of 20 is 10100. After setting even bits, we get 11110 Input : 10 Output : 10
Method 1:
- First, generate a number that contains even position bits.
- Take OR with the original number. Note that 1 | 1 = 1 and 1 | 0 = 1.
Let’s understand this approach with the below code.
C++
// Simple CPP program to set all even // bits of a number #include <iostream> using namespace std; // Sets even bits of n and returns // modified number. int evenbitsetnumber( int n) { // Generate 101010...10 number and // store in res. int count = 0, res = 0; for ( int temp = n; temp > 0; temp >>= 1) { // if bit is even then generate // number and or with res if (count % 2 == 1) res |= (1 << count); count++; } // return OR number return (n | res); } int main() { int n = 10; cout << evenbitsetnumber(n); return 0; } |
Java
// Simple Java program to set all even // bits of a number class GFG { // Sets even bits of n and returns // modified number. static int evenbitsetnumber( int n) { // Generate 101010...10 number and // store in res. int count = 0 , res = 0 ; for ( int temp = n; temp > 0 ; temp >>= 1 ) { // if bit is even then generate // number and or with res if (count % 2 == 1 ) res |= ( 1 << count); count++; } // return OR number return (n | res); } // Driver code public static void main(String[] args) { int n = 4 ; System.out.println(evenbitsetnumber(n)); } } // This code is contributed // by prerna saini. |
Python3
# Simple Python program to set all even # bits of a number # Sets even bits of n and returns # modified number. def evenbitsetnumber(n): # Generate 101010...10 number and # store in res. count = 0 res = 0 temp = n while (temp > 0 ): # if bit is even then generate # number and or with res if (count % 2 = = 1 ): res | = ( 1 << count) count + = 1 temp >> = 1 # return OR number return (n | res) n = 10 print (evenbitsetnumber(n)) # This code is contributed # by Smitha Dinesh Semwal |
C#
// Simple C# program to set // all even bits of a number using System; class GFG { // Sets even bits of n and // returns modified number. static int evenbitsetnumber( int n) { // Generate 101010...10 number // and store in res. int count = 0, res = 0; for ( int temp = n; temp > 0; temp >>= 1) { // if bit is even then generate // number and or with res if (count % 2 == 1) res |= (1 << count); count++; } // return OR number return (n | res); } // Driver code public static void Main() { int n = 4; Console.WriteLine(evenbitsetnumber(n)); } } // This code is contributed by vt_m. |
PHP
<?php // Simple php program to set // all even bits of a number // Sets even bits of n and // returns modified number. function evenbitsetnumber( $n ) { // Generate 101010...10 number // and store in res. $count = 0; $res = 0; for ( $temp = $n ; $temp > 0; $temp >>= 1) { // if bit is even then generate // number and or with res if ( $count % 2 == 1) $res |= (1 << $count ); $count ++; } // return OR number return ( $n | $res ); } //Driver Code $n = 10; echo evenbitsetnumber( $n ); //This Code is contributed by mits ?> |
Javascript
<script> // JavaScript program to set all even // bits of a number // Sets even bits of n and returns // modified number. function evenbitsetnumber(n) { // Generate 101010...10 number and // store in res. let count = 0, res = 0; for (let temp = n; temp > 0; temp >>= 1) { // If bit is even then generate // number and or with res if (count % 2 == 1) res |= (1 << count); count++; } // Return OR number return (n | res); } // Driver Code let n = 10; document.write(evenbitsetnumber(n)); // This code is contributed by avijitmondal1998 </script> |
10
Method 2 (A O(1) solution for 32 bit numbers)
C++
// Efficient CPP program to set all even // bits of a number #include <iostream> using namespace std; // return msb set number int getmsb( int n) { // set all bits n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // return msb // increment n by 1 // and shift by 1 return (n + 1) >> 1; } // return even set number int getevenbits( int n) { // get msb here n = getmsb(n); // generate even bits like 101010.. n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // if bits is odd then shift by 1 if (n & 1) n = n >> 1; // return even set bits number return n; } // set all even bits here int setallevenbits( int n) { // take or with even set bits number return n | getevenbits(n); } int main() { int n = 10; cout << setallevenbits(n); return 0; } |
Java
// Efficient Java program to // set all even bits of a number import java.io.*; class GFG { // return msb set number static int getmsb( int n) { // set all bits n |= n >> 1 ; n |= n >> 2 ; n |= n >> 4 ; n |= n >> 8 ; n |= n >> 16 ; // return msb // increment n by 1 // and shift by 1 return (n + 1 ) >> 1 ; } // return even set number static int getevenbits( int n) { // get msb here n = getmsb(n); // generate even // bits like 101010.. n |= n >> 2 ; n |= n >> 4 ; n |= n >> 8 ; n |= n >> 16 ; // if bits is odd // then shift by 1 if ((n & 1 ) == 1 ) n = n >> 1 ; // return even // set bits number return n; } // set all even bits here static int setallevenbits( int n) { // take or with even // set bits number return n | getevenbits(n); } // Driver Code public static void main (String[] args) { int n = 10 ; System.out.println(setallevenbits(n)); } } // This code is contributed by ajit |
Python3
# Efficient Python 3 # program to set all even # bits of a number # return msb set number def getmsb(n): # set all bits n | = n >> 1 n | = n >> 2 n | = n >> 4 n | = n >> 8 n | = n >> 16 # return msb # increment n by 1 # and shift by 1 return (n + 1 ) >> 1 # return even set number def getevenbits(n): # get msb here n = getmsb(n) # generate even bits like 101010.. n | = n >> 2 n | = n >> 4 n | = n >> 8 n | = n >> 16 # if bits is odd then shift by 1 if (n & 1 ): n = n >> 1 # return even set bits number return n # set all even bits here def setallevenbits(n): # take or with even set bits number return n | getevenbits(n) n = 10 print (setallevenbits(n)) # This code is contributed by # Smitha Dinesh Semwal |
C#
// Efficient C# program to // set all even bits of a number using System; class GFG { // return msb set number static int getmsb( int n) { // set all bits n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // return msb // increment n by 1 // and shift by 1 return (n + 1) >> 1; } // return even set number static int getevenbits( int n) { // get msb here n = getmsb(n); // generate even // bits like 101010.. n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // if bits is odd // then shift by 1 if ((n & 1) == 1) n = n >> 1; // return even // set bits number return n; } // set all even bits here static int setallevenbits( int n) { // take or with even // set bits number return n | getevenbits(n); } // Driver Code public static void Main () { int n = 10; Console.WriteLine(setallevenbits(n)); } } // This code is contributed by aj_36 |
PHP
<?php // Efficient php program to set // all even bits of a number // return msb set number function getmsb( $n ) { // set all bits $n |= $n >> 1; $n |= $n >> 2; $n |= $n >> 4; $n |= $n >> 8; $n |= $n >> 16; // return msb // increment n by 1 // and shift by 1 return ( $n + 1) >> 1; } // return even set number function getevenbits( $n ) { // get msb here $n = getmsb( $n ); // generate even bits // like 101010.. $n |= $n >> 2; $n |= $n >> 4; $n |= $n >> 8; $n |= $n >> 16; // if bits is odd then // shift by 1 if ( $n & 1) $n = $n >> 1; // return even set // bits number return $n ; } // set all even bits here function setallevenbits( $n ) { // take or with even // set bits number return $n | getevenbits( $n ); } //Driver code $n = 10; echo setallevenbits( $n ); //This code is contributed by mits ?> |
Javascript
<script> // Efficient Javascript program to // set all even bits of a number // Return msb set number function getmsb(n) { // Set all bits n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Return msb // increment n by 1 // and shift by 1 return (n + 1) >> 1; } // Return even set number function getevenbits(n) { // Get msb here n = getmsb(n); // Generate even // bits like 101010.. n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // If bits is odd // then shift by 1 if ((n & 1) == 1) n = n >> 1; // Return even // set bits number return n; } // Set all even bits here function setallevenbits(n) { // Take or with even // set bits number return n | getevenbits(n); } // Driver code let n = 10; document.write(setallevenbits(n)); // This code is contributed by decode2207 </script> |
10
Method 3: Using bit mask
To set a bit, we can take OR of 1 and that bit (as 1 | 1 = 1, and 1 | 0 = 1). Therefore, to set all odd bits of an n-bit number, we need to use a bit mask which is an n-bit binary number with all odd bits set. This mask can be generated in 1 step using the formula of sum of a geometric progression, as an n bit number …1010 is equal to 21 + 23 + 25 + …. 2 (n – !(n % 1)) .
Approach:
- Calculate the number of bits using log2(number)
- Calculate the largest power m, of the GP series using the formula (numOfBits – !(numOfBits % 1)).
- Calculate the value of the mask using the formula: a × (r m + 1 – 1) / (r – 1).
- Perform the setting operation using number | mask.
C++
// Simple CPP program to set all even // bits of a number #include <bits/stdc++.h> using namespace std; //function to set all the even bits long long int setEvenBits( long long int n) { //calculating number of bits using log int numOfBits = 1 + ( int )log2(n); //if there is only one bit, if (numOfBits == 1) return n; //calculating the max power of GP series int m = (numOfBits - !(numOfBits % 1)) / 2 ; //calculating mask using GP sum //which is a(r ^ n - 1) / (r - 1) //where a = 2, r = 4, n = m int mask = (2 * ((1 << (2 * m)) - 1)) / 3; //toggling all even bits using mask | n return mask | n; } //Driver Code int main() { int n = 102121; cout << setEvenBits(n); return 0; } //This approach is contributed by phasing17 |
Java
// Simple Java program to set all even // bits of a number import java.util.*; class GFG { // function to set all the even bits static int setEvenBits( int n) { // calculating number of bits using log int numOfBits = 1 + ( int )(Math.log(n) / Math.log( 2 )); // if there is only one bit, if (numOfBits == 1 ) return n; // calculating the max power of GP series int m = (numOfBits - 1 ^ (numOfBits % 1 )) / 2 ; // calculating mask using GP sum // which is a(r ^ n - 1) / (r - 1) // where a = 2, r = 4, n = m int mask = ( 2 * (( 1 << ( 2 * m)) - 1 )) / 3 ; // toggling all even bits using mask | n return mask | n; } // Driver Code public static void main(String[] args) { int n = 102121 ; System.out.println(setEvenBits(n)); } } // This code is contributed by phasing17 |
Python3
# Simple Python3 program to set all even # bits of a number from math import log # function to set all the even bits def setEvenBits(n): # calculating number of bits using log numOfBits = 1 + int (log(n, 2 )) # if there is only one bit, if numOfBits = = 1 : return n # calculating the max power of GP series m = int ((numOfBits - 1 ^ (numOfBits % 1 )) / 2 ) # calculating mask using GP sum # which is a(r ^ n - 1) / (r - 1) # where a = 2, r = 4, n = m mask = int (( 2 * (( 1 << ( 2 * m)) - 1 )) / 3 ) # toggling all even bits using mask | n return mask | n # Driver Code n = 102121 print (setEvenBits(n)) # This code is contributed by phasing17 |
C#
// Simple C# program to set all even // bits of a number using System; class GFG { // function to set all the even bits static int setEvenBits( int n) { // calculating number of bits using log int numOfBits = 1 + ( int )(Math.Log(n) / Math.Log(2)); // if there is only one bit, if (numOfBits == 1) return n; // calculating the max power of GP series int m = (numOfBits - 1 ^ (numOfBits % 1)) / 2; // calculating mask using GP sum // which is a(r ^ n - 1) / (r - 1) // where a = 2, r = 4, n = m int mask = (2 * ((1 << (2 * m)) - 1)) / 3; // toggling all even bits using mask | n return mask | n; } // Driver Code public static void Main( string [] args) { int n = 102121; Console.WriteLine(setEvenBits(n)); } } // This code is contributed by phasing17 |
Javascript
// Simple JavaScript program to set all even // bits of a number // function to set all the even bits function setEvenBits(n) { // calculating number of bits using log let numOfBits = 1 + Math.floor(Math.log2(n)); // if there is only one bit, if (numOfBits == 1) return n; // calculating the max power of GP series let m = Math.floor((numOfBits - !(numOfBits % 1)) / 2); // calculating mask using GP sum // which is a(r ^ n - 1) / (r - 1) // where a = 2, r = 4, n = m let mask = Math.floor((2 * ((1 << (2 * m)) - 1)) / 3); // toggling all even bits using mask | n return mask | n; } // Driver Code let n = 102121; console.log(setEvenBits(n)); // This approach is contributed by phasing17 |
110315
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us