Увеличьте число, переставив биты

Опубликовано: 17 Января, 2022

Учитывая беззнаковое число, найдите максимальное число, которое может быть образовано с использованием битов данного беззнакового числа.
Примеры :

 Ввод: 1 (0000 .... 0001)
Выход: 2147483648 (1000 .... 0000)

Ввод: 7 (0000 .... 0111)
Выход: 3758096384 (0111 .... 0000)

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Method 1 (Simple)
1. Find binary representation of the number using simple decimal to binary representation technique.
2. Count number of set bits in the binary representation equal to ‘n’.
3. Create a binary representation with its ‘n’ most significant bits set to 1.
4. Convert the binary representation back to the number.

C++

// An simple C++ program to find
// minimum number formed by bits of a
// given number.
#include <bits/stdc++.h>
#define ll unsigned int
using namespace std;
 
// Returns maximum number formed by
// bits of a given number.
ll maximize(ll a)
{
    // _popcnt32(a) gives number of 1"s
    // present in binary representation of a.
    ll n = _popcnt32(a);
 
    // Set most significant n bits of res.
    ll res = 0;
    for (int i=1; i<=n; i++)
       res |= (1 << (32 - i));
 
    return res;
}
 
// Driver function.
int main()
{
    ll a = 1;
    cout << maximize(a) << endl;
    return 0;
}

Java

// An simple Java program to find
// minimum number formed by bits
// of a given number.
import java.io.*;
 
class GFG
{
    private static int _popcnt32(long number)
    {
        int counter = 0;
         
        while(number > 0)
        {
            if(number % 2 == 1)
            {
                counter++;
            }
             
            //or number = number >> 1
            number = number / 2;
        }
        return counter;
    }
     
    // Returns maximum number formed
    // by bits of a given number.
    static long maximize(long a)
    {
        // _popcnt32(a) gives number
        // of 1"s present in binary
        // representation of a.
        int n = _popcnt32(a);
                 
        // Set most significant
        // n bits of res.
        long res = 0;
        for (int i = 1; i <= n; i++)
        res = (int)res | (1 << (32 - i));
     
        return Math.abs(res);
    }
     
    // Driver Code
    public static void main(String args[])
    {
        long a = 1;
        System.out.print(maximize(a));
    }
}
 
// This code is contributed by
// Manish Shaw(manishshaw1)

Python3

# An simple Python program to
# find minimum number formed
# by bits of a given number.
def _popcnt32(number) :
    counter = 0
     
    while(number > 0) :
        if(number % 2 == 1) :
            counter = counter + 1
             
        # or number = number >> 1
        number = int(number / 2)
 
    return counter
 
# Returns maximum number formed
# by bits of a given number.
def maximize(a) :
     
    # _popcnt32(a) gives number
    # of 1"s present in binary
    # representation of a.
    n = _popcnt32(a)
             
    # Set most significant
    # n bits of res.
    res = 0
    for i in range(1, n + 1) :
        res = int(res |
                 (1 << (32 - i)))
 
    return abs(res)
 
# Driver Code
a = 1
print (maximize(a))
 
# This code is contributed by
# Manish Shaw(manishshaw1)

C#

// An simple C# program to find
// minimum number formed by bits
// of a given number.
using System;
 
class GFG
{
     
    // Returns maximum number formed
    // by bits of a given number.
    static long maximize(long a)
    {
        // _popcnt32(a) gives number
        // of 1"s present in binary
        // representation of a.
        string binaryString = Convert.ToString(a, 2);
        int n = binaryString.Split(new [] {"0"},
                StringSplitOptions.RemoveEmptyEntries).Length;
                 
        // Set most significant n bits of res.
        long res = 0;
        for (int i = 1; i <= n; i++)
        res = (int)res | (1 << (32 - i));
     
        return Math.Abs(res);
    }
     
    // Driver Code.
    static void Main()
    {
        long a = 1;
        Console.WriteLine(maximize(a));
    }
}
// This code is contributed by
// Manish Shaw(manishshaw1)

PHP

<?php
// An simple PHP program to find
// minimum number formed by bits
// of a given number.
function _popcnt32($number)
{
    $counter = 0;
     
    while($number > 0)
    {
        if($number % 2 == 1)
        {
            $counter++;
        }
         
        //or number = number >> 1
        $number = intval($number / 2);
    }
    return $counter;
}
 
// Returns maximum number formed
// by bits of a given number.
function maximize($a)
{
    // _popcnt32(a) gives number
    // of 1"s present in binary
    // representation of a.
    $n = _popcnt32($a);
             
    // Set most significant
    // n bits of res.
    $res = 0;
    for ($i = 1; $i <= $n; $i++)
    $res = intval($res |
                 (1 << (32 - $i)));
 
    return abs($res);
}
 
// Driver Code
$a = 1;
echo (maximize($a));
 
// This code is contributed by
// Manish Shaw(manishshaw1)
?>

Javascript

<script>
  
// An simple JavaScript program to find
// minimum number formed by bits of a
// given number.
 
 
function _popcnt32(number)
{
    var counter = 0;
     
    while(number > 0)
    {
        if(number % 2 == 1)
        {
            counter++;
        }
         
        //or number = number >> 1
        number = parseInt(number / 2);
    }
    return counter;
}
 
// Returns maximum number formed by
// bits of a given number.
function maximize(a)
{
    // _popcnt32(a) gives number of 1"s
    // present in binary representation of a.
    var n = _popcnt32(a);
 
    // Set most significant n bits of res.
    var res = 0;
    for (var i=1; i<=n; i++)
       res |= (1 << (32 - i));
 
    return Math.abs(res);
}
 
// Driver function.
var a = 1;
document.write(maximize(a));
 
</script>

Output:

2147483648

Метод 2 (эффективный)
Идея состоит в том, чтобы сначала найти число с n наименее значимыми установленными битами, а затем сдвинуть число влево на 32-n.

Примечание. В приведенных выше кодах используются специальные функции GCC. Если мы хотим написать код для других компиляторов, мы можем использовать биты набора Count в виде целого числа.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Увеличьте число, переставив биты

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ