Dado un número, encuentre el número mayor menor que el número dado que es la potencia de dos o encuentre el número de bits más significativo.
Ejemplos:
Input : 10 Output : 8 Greatest number which is a Power of 2 less than 10 is 8 Binary representation of 10 is 1010 The most significant bit corresponds to decimal number 8. Input : 18 Output : 16
Una solución simple es dividir n uno por uno entre 2 hasta que se convierta en 0 e incrementar un conteo mientras se hace esto. Este conteo en realidad representa la posición de MSB.
C++
// Simple CPP program to find MSB number
// for given POSITIVE n.
#include <iostream>
using namespace std;
int setBitNumber(int n)
{
if (n == 0)
return 0;
int msb = 0;
n = n / 2;
while (n != 0) {
n = n / 2;
msb++;
}
return (1 << msb);
}
// Driver code
int main()
{
int n = 0;
cout << setBitNumber(n);
n = ~(int)0; // test for possible overflow
cout << "\n" << (unsigned int)setBitNumber(n);
return 0;
}
C
#include <stdio.h>
int setBitNumber(int n)
{
if (n == 0)
return 0;
int msb = 0;
n = n / 2;
while (n != 0) {
n = n / 2;
msb++;
}
return (1 << msb);
}
int main() {
int n = 0;
printf("%d \n",setBitNumber(n));
n = ~(int)0; // test for possible overflow
int ns = (unsigned int)setBitNumber(n);
printf("%d",ns);
return 0;
}
Java
// Simple Java program to find
// MSB number for given n.
import java.io.*;
class GFG {
static int setBitNumber(int n)
{
if (n == 0)
return 0;
int msb = 0;
n = n / 2;
while (n != 0) {
n = n / 2;
msb++;
}
return (1 << msb);
}
// Driver code
public static void main(String[] args)
{
int n = 0;
System.out.println(setBitNumber(n));
}
}
// This code is contributed by ajit
Python3
# Simple Python3 program # to find MSB number # for given n. def setBitNumber(n): if (n == 0): return 0; msb = 0; n = int(n / 2); while (n > 0): n = int(n / 2); msb += 1; return (1 << msb); # Driver code n = 0; print(setBitNumber(n)); # This code is contributed # by mits
C#
// Simple C# program to find
// MSB number for given n.
using System;
class GFG {
static int setBitNumber(int n)
{
if (n == 0)
return 0;
int msb = 0;
n = n / 2;
while (n != 0) {
n = n / 2;
msb++;
}
return (1 << msb);
}
// Driver code
static public void Main()
{
int n = 0;
Console.WriteLine(setBitNumber(n));
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// Simple PhP program
// to find MSB number
// for given n.
function setBitNumber($n)
{
if ($n == 0)
return 0;
$msb = 0;
$n = $n / 2;
while ($n != 0)
{
$n = $n / 2;
$msb++;
}
return (1 << $msb);
}
// Driver code
$n = 0;
echo setBitNumber($n);
// This code is contributed
// by akt_mit
?>
Javascript
<script>
// Javascript program
// to find MSB number
// for given n.
function setBitNumber(n)
{
if (n == 0)
return 0;
let msb = 0;
n = n / 2;
while (n != 0)
{
n = $n / 2;
msb++;
}
return (1 << msb);
}
// Driver code
let n = 0;
document.write (setBitNumber(n));
// This code is contributed by Bobby
</script>
Producción:
0
Una solución eficiente para un número entero de tamaño fijo (digamos 32 bits) es establecer bits uno por uno, luego agregar 1 para que solo se establezca el bit después de MSB. Finalmente, desplácese a la derecha en 1 y devuelva la respuesta. Esta solución no requiere ninguna verificación de condición.
C++
// CPP program to find MSB number for ANY given n.
#include <iostream>
#include <limits.h>
using namespace std;
int setBitNumber(int n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// The naive approach would increment n by 1,
// so only the MSB+1 bit will be set,
// So now n theoretically becomes 1000000000.
// All the would remain is a single bit right shift:
// n = n + 1;
// return (n >> 1);
//
// ... however, this could overflow the type.
// To avoid overflow, we must retain the value
// of the bit that could overflow:
// n & (1 << ((sizeof(n) * CHAR_BIT)-1))
// and OR its value with the naive approach:
// ((n + 1) >> 1)
n = ((n + 1) >> 1) |
(n & (1 << ((sizeof(n) * CHAR_BIT)-1)));
return n;
}
// Driver code
int main()
{
int n = 273;
cout << setBitNumber(n);
n = ~(int)0; // test for possible overflow
cout << "\n" << (unsigned int)setBitNumber(n);
return 0;
}
C
#include <stdio.h>
#include <limits.h>
int setBitNumber(int n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// The naive approach would increment n by 1,
// so only the MSB+1 bit will be set,
// So now n theoretically becomes 1000000000.
// All the would remain is a single bit right shift:
// n = n + 1;
// return (n >> 1);
//
// ... however, this could overflow the type.
// To avoid overflow, we must retain the value
// of the bit that could overflow:
// n & (1 << ((sizeof(n) * CHAR_BIT)-1))
// and OR its value with the naive approach:
// ((n + 1) >> 1)
n = ((n + 1) >> 1) |
(n & (1 << ((sizeof(n) * CHAR_BIT)-1)));
return n;
}
int main() {
int n = 273;
printf("%d\n",setBitNumber(n));
return 0;
}
Java
// Java program to find MSB
// number for given n.
class GFG {
static int setBitNumber(int n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Increment n by 1 so that
// there is only one set bit
// which is just before original
// MSB. n now becomes 1000000000
n = n + 1;
// Return original MSB after shifting.
// n now becomes 100000000
return (n >> 1);
}
// Driver code
public static void main(String arg[])
{
int n = 273;
System.out.print(setBitNumber(n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find # MSB number for given n. def setBitNumber(n): # Below steps set bits after # MSB (including MSB) # Suppose n is 273 (binary # is 100010001). It does following # 100010001 | 010001000 = 110011001 n |= n>>1 # This makes sure 4 bits # (From MSB and including MSB) # are set. It does following # 110011001 | 001100110 = 111111111 n |= n>>2 n |= n>>4 n |= n>>8 n |= n>>16 # Increment n by 1 so that # there is only one set bit # which is just before original # MSB. n now becomes 1000000000 n = n + 1 # Return original MSB after shifting. # n now becomes 100000000 return (n >> 1) # Driver code n = 273 print(setBitNumber(n)) # This code is contributed # by Anant Agarwal.
C#
// C# program to find MSB number for given n.
using System;
class GFG {
static int setBitNumber(int n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Increment n by 1 so that
// there is only one set bit
// which is just before original
// MSB. n now becomes 1000000000
n = n + 1;
// Return original MSB after shifting.
// n now becomes 100000000
return (n >> 1);
}
// Driver code
public static void Main()
{
int n = 273;
Console.WriteLine(setBitNumber(n));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to find
// MSB number for given n.
function setBitNumber($n)
{
// Below steps set bits
// after MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does
// following 100010001 |
// 010001000 = 110011001
$n |= $n >> 1;
// This makes sure 4 bits
// (From MSB and including
// MSB) are set. It does
// following 110011001 |
// 001100110 = 111111111
$n |= $n >> 2;
$n |= $n >> 4;
$n |= $n >> 8;
$n |= $n >> 16;
// Increment n by 1 so
// that there is only
// one set bit which is
// just before original
// MSB. n now becomes
// 1000000000
$n = $n + 1;
// Return original MSB
// after shifting. n
// now becomes 100000000
return ($n >> 1);
}
// Driver code
$n = 273;
echo setBitNumber($n);
// This code is contributed
// by akt_mit
?>
Javascript
<script>
// Javascript program to find MSB
// number for given n.
function setBitNumber(n)
{
// Below steps set bits after
// MSB (including MSB)
// Suppose n is 273 (binary
// is 100010001). It does following
// 100010001 | 010001000 = 110011001
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set. It does following
// 110011001 | 001100110 = 111111111
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Increment n by 1 so that
// there is only one set bit
// which is just before original
// MSB. n now becomes 1000000000
n = n + 1;
// Return original MSB after shifting.
// n now becomes 100000000
return (n >> 1);
}
// Driver code
let n = 273;
document.write(setBitNumber(n));
// This code is contributed by suresh07
</script>
Producción:
256
La complejidad del tiempo es O(1).
Otro enfoque: dado un número n. Primero, encuentre la posición del bit establecido más significativo y luego calcule el valor del número con un bit establecido en la posición k-ésima.
Gracias Rohit Narayan por sugerir este método.
C++
// CPP program to find MSB
// number for given POSITIVE n.
#include <bits/stdc++.h>
using namespace std;
int setBitNumber(int n)
{
// To find the position
// of the most significant
// set bit
int k = (int)(log2(n));
// To return the value
// of the number with set
// bit at k-th position
return 1 << k;
}
// Driver code
int main()
{
int n = 273;
cout << setBitNumber(n);
n = ~(int)0; // test for possible overflow
cout << "\n" << (unsigned int)setBitNumber(n);
return 0;
}
C
#include <stdio.h>
#include <math.h>
int setBitNumber(int n)
{
// To find the position
// of the most significant
// set bit
int k = (int)(log2(n));
// To return the value
// of the number with set
// bit at k-th position
return 1 << k;
}
int main() {
int n = 273;
printf("%d",setBitNumber(n));
return 0;
}
Java
// Java program to find MSB
// number for given n.
class GFG {
static int setBitNumber(int n)
{
// To find the position of the
// most significant set bit
int k = (int)(Math.log(n) / Math.log(2));
// To return the value of the number
// with set bit at k-th position
return 1 << k;
}
// Driver code
public static void main(String arg[])
{
int n = 273;
System.out.print(setBitNumber(n));
}
}
Python3
# Python program to find # MSB number for given n. import math def setBitNumber(n): # To find the position of # the most significant # set bit k = int(math.log(n, 2)) # To return the value # of the number with set # bit at k-th position return 1 << k # Driver code n = 273 print(setBitNumber(n))
C#
// C# program to find MSB
// number for given n.
using System;
public class GFG {
static int setBitNumber(int n)
{
// To find the position of the
// most significant set bit
int k = (int)(Math.Log(n) / Math.Log(2));
// To return the value of the number
// with set bit at k-th position
return 1 << k;
}
// Driver code
static public void Main()
{
int n = 273;
Console.WriteLine(setBitNumber(n));
}
}
PHP
<?php
// PHP program to find MSB
// number for given n.
function setBitNumber($n)
{
// To find the position
// of the most significant
// set bit
$k =(int)(log($n, 2));
// To return the value
// of the number with set
// bit at k-th position
return 1 << $k;
}
// Driver code
$n = 273;
echo setBitNumber($n);
// This code is contributed
// by jit_t.
?>
Javascript
<script>
// Javascript program to find
// MSB number for given n.
function setBitNumber(n)
{
// To find the position of the
// most significant set bit
let k = parseInt(Math.log(n) / Math.log(2), 10);
// To return the value of the number
// with set bit at k-th position
return 1 << k;
}
let n = 273;
document.write(setBitNumber(n));
</script>
Producción:
256
Otro enfoque :
Este artículo es una contribución de Devanshu Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA