Alternar bits de un número excepto el primero y el último bit

Posted on by Rudeus Greyrat

Dado un número, la tarea es alternar bits del número excepto el primero y el último bit.
Ejemplos: 

Input : 10
Output : 12
Binary representation:- 1 0 1 0
After toggling first and last : 1 1 0 0

Input : 9
Output : 15
Binary representation : 1 0 0 1
After toggling first and last : 1 1 1 1

Requisito previo: encontrar el conjunto de bits más significativo de un número

  1. Genere un número que contenga el bit del medio como un conjunto. Necesitamos cambiar todos los bits intermedios a 1 y mantener los bits de las esquinas como 
  2. La respuesta es XOR del número generado y el número original. Tenga en cuenta que XOR de 1 con un número alterna el número.

C++

// C++ Program to toggle bits
// except first and last bit
#include<iostream>
using namespace std;
 
// return set middle bits
int setmiddlebits(int n)
{
 
    // set all bit
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
 
    // return middle set bits
    // shift by 1 and xor with 1
    return (n >> 1) ^ 1;
}
 
int togglemiddlebits(int n)
{
     
    // if number is 1 then
    // simply return
    if (n == 1)
        return 1;
 
    // xor with
    // middle bits
    return n ^ setmiddlebits(n);
}
 
// Driver Code
int main()
{
     
    // Given number
    int n = 9;
 
    // print toggle bits
    cout<<togglemiddlebits(n);
 
    return 0;
}

Java

// Java program for toggle bits
// expect first and last bit
import java.io.*;
 
class GFG {
     
    // return set middle bits
    static int setmiddlebits(int n)
    {
 
        // set all bit
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
     
        // return middle set bits
        // shift by 1 and xor with 1
        return (n >> 1) ^ 1;
    }
 
    static int togglemiddlebits(int n)
    {
        // if number is 1 then
        // simply return
        if (n == 1)
            return 1;
     
        // XOR with middle bits
        return n ^ setmiddlebits(n);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
     
        // Given number
        int n = 9;
     
        // print toggle bits
        System.out.println(togglemiddlebits(n));
    }
}
 
// This code is contributed by vt_m

Python3

# Python3 program for toggle bits
# expect first and last bit
 
# return set middle bits
def setmiddlebits(n):
 
    # set all bit
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
 
    # return middle set bits
    # shift by 1 and xor with 1
    return (n >> 1) ^ 1
 
def togglemiddlebits(n):
 
    # if number is 1 then simply return
    if (n == 1):
        return 1
 
    # xor with middle bits
    return n ^ setmiddlebits(n)
 
# Driver code
n = 9
print(togglemiddlebits(n))
 
# This code is contributed by Anant Agarwal.

C#

// C# program for toggle bits
// expect first and last bit
using System;
 
class GFG {
     
    // return set middle bits
    static int setmiddlebits(int n)
    {
 
        // set all bit
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
         
        // return middle set bits
        // shift by 1 and xor with 1
        return (n >> 1) ^ 1;
    }
 
    static int togglemiddlebits(int n)
    {
         
        // if number is 1 then
        // simply return
        if (n == 1)
            return 1;
     
        // XOR with middle bits
        return n ^ setmiddlebits(n);
    }
     
    // Driver Code
    public static void Main ()
    {
     
        // Given number
        int n = 9;
     
        // print toggle bits
        Console.WriteLine(togglemiddlebits(n));
    }
}
 
// This code is contributed by Anant Agarwal.

PHP

<?php
// Php Program to toggle bits
// except first and last bit
 
// return set middle bits
function setmiddlebits($n)
{
 
    // set all bit
    $n |= $n >> 1;
    $n |= $n >> 2;
    $n |= $n >> 4;
    $n |= $n >> 8;
    $n |= $n >> 16;
 
    // return middle set bits
    // shift by 1 and xor with 1
    return ($n >> 1) ^ 1;
}
 
function togglemiddlebits($n)
{
     
    // if number is 1 then
    // simply return
    if ($n == 1)
        return 1;
 
    // xor with
    // middle bits
    return $n ^ setmiddlebits($n);
}
 
    // Driver Code
    $n = 9;
 
    // print toggle bits
    echo togglemiddlebits($n);
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Javascript Program to toggle bits
// except first and last bit
 
// return set middle bits
function setmiddlebits(n)
{
 
    // set all bit
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
 
    // return middle set bits
    // shift by 1 and xor with 1
    return (n >> 1) ^ 1;
}
 
function togglemiddlebits(n)
{
     
    // if number is 1 then
    // simply return
    if (n == 1)
        return 1;
 
    // xor with
    // middle bits
    return n ^ setmiddlebits(n);
}
 
// Driver Code
 
// Given number
var n = 9;
// print toggle bits
document.write(togglemiddlebits(n));
     
</script>
Producción

15

Complejidad de tiempo: O(log 2 n), donde n es el número dado 
Espacio auxiliar: O(1)
 

Otro enfoque : uso de máscara de bits
La idea para resolver este problema es que podemos usar XOR de un bit específico con 1 para alternar el bit específico. Por lo tanto, para un número de n bits, podemos construir una máscara de bits de la forma 0111….11110, es decir, un número de n bits, donde se establecen todos los bits excepto el primero y el último. Por lo tanto, para un número que es mayor o igual a 4, la máscara de bits es igual a 2n – 2. (n se puede calcular utilizando el número log 2 ) (Para números menores a 4, no hay bits intermedios, por lo tanto, el el número no se cambiará).

Acercarse:

  1. Calcular la máscara de bits = 2 log 2 número – 2
  2. Realiza el XOR del número y la máscara.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ Program to toggle bits
// except first and last bit
#include<bits/stdc++.h>
using namespace std;
 
 
//function to toggle the middle bits
//using the bit mask
int togglemiddlebits(int n)
{
    //if n < 4, there are no middle bits
    if (n < 4)
        return n;
    int mask = (1 << (int)log2(n)) - 2;
    return mask ^ n;
}
 
// Driver Code
int main()
{
     
    // Given number
    int n = 9;
     
    //Function call
    cout << togglemiddlebits(n) << endl;
 
    return 0;
}
 
//This code is contributed by phasing17

C#

// C# Program to toggle bits
// except first and last bit
 
using System;
 
class GFG {
 
  // function to toggle the middle bits
  // using the bit mask
  static int togglemiddlebits(int n)
  {
    // if n < 4, there are no middle bits
    if (n < 4)
      return n;
    int mask
      = (1 << (int)(Math.Log(n) / Math.Log(2))) - 2;
    return mask ^ n;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    // Given number
    int n = 9;
 
    // Function call
    Console.WriteLine(togglemiddlebits(n));
  }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript Program to toggle bits
// except first and last bit
 
 
//Function to toggle the middle bits
//using the bit mask
function togglemiddlebits(n)
{
 
    //if n < 4, there are no middle bits
    if (n < 4)
        return n;
    let mask = (1 << Math.floor(Math.log2(n))) - 2;
    return mask ^ n;
}
 
// Driver Code
// Given number
let n = 9;
     
//Function call
console.log(togglemiddlebits(n));
 
 
//This code is contributed by phasing17
Producción

15

Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *