Unset the last m bits
Given a non-negative number n. The problem is to unset the last m bits in the binary representation of n.
Constraint: 1 <= m <= num, where num is the number of bits in the binary representation of n.
Examples:
Input : n = 10, m = 2 Output : 8 (10)10 = (1010)2 (8)10 = (1000)2 The last two bits in the binary representation of 10 have been unset. Input : n = 150, m = 4 Output : 144
Approach: Following are the steps:
- Calculate num = (1 << (sizeof(int) * 8 – 1)) – 1. This will produce the highest positive integer num. All the bits in num will be set.
- Toggle the last m bits in num. Refer this post.
- Now, perform n = n & num. This will unset the last m bits in n.
- Return n.
Note: The sizeof(int) has been used as input is of int data type. For large inputs you can use long int or long long int datatypes in place of int.
C++
// C++ implementation to unset bits the last m bits #include <bits/stdc++.h> using namespace std; // function to toggle the last m bits unsigned int toggleLastMBits(unsigned int n, unsigned int m) { // calculating a number 'num' having 'm' bits // and all are set unsigned int num = (1 << m) - 1; // toggle the last m bits and return the number return (n ^ num); } // function to unset bits the last m bits unsigned int unsetLastMBits(unsigned int n, unsigned int m) { // 'num' is the highest positive integer number // all the bits of 'num' are set unsigned int num = (1 << ( sizeof ( int ) * 8 - 1)) - 1; // toggle the last 'm' bits in 'num' num = toggleLastMBits(num, m); // unset the last 'm' bits in 'n' // and return the number return (n & num); } // Driver program to test above int main() { unsigned int n = 150, m = 4; cout << unsetLastMBits(n, m); return 0; } |
Java
// Java implementation to unset // bits the last m bits class GFG { static int sizeofInt = 8 ; // function to toggle the last m bits static int toggleLastMBits( int n, int m) { // calculating a number 'num' having 'm' bits // and all are set int num = ( 1 << m) - 1 ; // toggle the last m bits and return the number return (n ^ num); } // function to unset bits the last m bits static int unsetLastMBits( int n, int m) { // 'num' is the highest positive integer number // all the bits of 'num' are set int num = ( 1 << (sizeofInt * 8 - 1 )) - 1 ; // toggle the last 'm' bits in 'num' num = toggleLastMBits(num, m); // unset the last 'm' bits in 'n' // and return the number return (n & num); } // Driver code public static void main(String[] args) { int n = 150 , m = 4 ; System.out.println(unsetLastMBits(n, m)); } } /* This code is contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation to unset # bits the last m bits import sys # function to toggle the last m bits def toggleLastMBits (n, m): # calculating a number 'num' # having 'm' bits and all are set num = ( 1 << m) - 1 # toggle the last m bits # and return the number return (n ^ num) # function to unset bits # the last m bits def unsetLastMBits(n, m): # 'num' is the highest positive integer # number all the bits of 'num' are set num = ( 1 << (sys.getsizeof( int ) * 8 - 1 )) - 1 # toggle the last 'm' bits in 'num' num = toggleLastMBits(num, m) # unset the last 'm' bits in 'n' # and return the number return (n & num) # Driven code n = 150 m = 4 print (unsetLastMBits(n, m)) # This code is contributed by "rishabh_jain". |
C#
// C# implementation to unset // bits the last m bits using System; class GFG { static int sizeofInt = 8; // function to toggle the last m bits static int toggleLastMBits( int n, int m) { // calculating a number 'num' having 'm' bits // and all are set int num = (1 << m) - 1; // toggle the last m bits and return the number return (n ^ num); } // function to unset bits the last m bits static int unsetLastMBits( int n, int m) { // 'num' is the highest positive integer number // all the bits of 'num' are set int num = (1 << (sizeofInt * 8 - 1)) - 1; // toggle the last 'm' bits in 'num' num = toggleLastMBits(num, m); // unset the last 'm' bits in 'n' // and return the number return (n & num); } // Driver code public static void Main(String[] args) { int n = 150, m = 4; Console.WriteLine(unsetLastMBits(n, m)); } } // This code is contributed by Rajput-Ji |
PHP
<?php // php implementation to unset // bits the last m bits // function to toggle // the last m bits function toggleLastMBits( $n , $m ) { // calculating a number 'num' // having 'm' bits // and all are set $num = (1 << $m ) - 1; // toggle the last m bits // and return the number return ( $n ^ $num ); } // function to unset bits // the last m bits function unsetLastMBits( $n , $m ) { // 'num' is the highest positive // integer number all the bits // of 'num' are set //4 is Size of integer 32 bit $num = (1 << (4 * 8 - 1)) - 1; // toggle the last 'm' bits in 'num' $num = toggleLastMBits( $num , $m ); // unset the last 'm' bits in 'n' // and return the number return ( $n & $num ); } // Drivercode $n = 150; $m = 4; echo unsetLastMBits( $n , $m ); // This code is contributed by mits ?> |
Javascript
<script> // JavaScript implementation to unset // bits the last m bits let sizeofLet = 8; // Function to toggle the last m bits function toggleLastMBits(n, m) { // Calculating a number 'num' having // 'm' bits and all are set let num = (1 << m) - 1; // Toggle the last m bits and // return the number return (n ^ num); } // Function to unset bits the last m bits function unsetLastMBits(n, m) { // 'num' is the highest positive // integer number all the bits of // 'num' are set let num = (1 << (sizeofLet * 8 - 1)) - 1; // Toggle the last 'm' bits in 'num' num = toggleLastMBits(num, m); // unset the last 'm' bits in 'n' // and return the number return (n & num); } // Driver Code let n = 150, m = 4; document.write(unsetLastMBits(n, m)); // This code is contributed by sanjoy_62 </script> |
Output:
144
Time Complexity: O(1)
Auxiliary Space: O(1)