Problema de Josephus usando Bit Magic

El problema

Este problema lleva el nombre de Flavio Josefo, un historiador judío que luchó contra los romanos. Según Josefo, él y su grupo de soldados judíos fueron acorralados y rodeados por los romanos dentro de una cueva, y optaron por asesinar y suicidarse antes de rendirse y capturar. Decidieron que todos los soldados se sentarían en círculo y comenzando por el soldado sentado en la primera posición, cada soldado mataría al soldado secuencialmente. Entonces, si hay 5 soldados sentados en un círculo con posiciones numeradas como 1, 2, 3, 4, 5. El soldado 1 mata a 2, luego 3 mata a 4, luego 5 mata a 1, luego 3 mata a 5, y como 3 es el solo queda uno, luego 3 se suicidan. 
Ahora Josefo no quiere ser asesinado o suicidarse. Preferiría ser capturado por los romanos y se le presenta un problema. Tiene que averiguar en qué posición debe sentarse en un círculo (siempre que haya n hombres en total y el hombre sentado en la posición 1 tenga la primera oportunidad de asesinar) para que sea el último hombre en pie y en lugar de suicidarse. se rendirá a los romanos.
 

El patrón

Si resuelve esto para diferentes valores de n, encontrará un patrón aquí. Si n es una verdadera potencia de 2, entonces la respuesta siempre es 1. Por cada n mayor que esa potencia de 2, la respuesta se incrementa en 2.  

Ahora, para cada n, la posición correcta para Josefo se puede encontrar restando la mayor potencia posible de 2 del número y obtenemos la respuesta (siempre que el valor de n no sea una potencia pura de 2, de lo contrario, la respuesta es 1)  

n = 2 ^a + algo

donde a = la mayor potencia posible

El truco
Cada vez que alguien habla de los poderes de 2, la primera palabra que viene a la mente es «binario». La solución a este problema es mucho más fácil y corta en binario que en decimal. Hay un truco para esto. Dado que necesitamos deducir la mayor potencia posible de en binario, ese número es el bit más significativo. En el problema original de Josefo, había otros 40 soldados junto con Josefo, lo que hace n = 41 . 41 en binario es 101001. Si cambiamos el MSB, es decir, el 1 más a la izquierda al lugar más a la derecha, obtenemos 010011, que es 19 (en decimal), que es la respuesta. Esto es cierto para todos los casos. Esto se puede hacer fácilmente usando la manipulación de bits.

// C++ program for josephus problem
#include <bits/stdc++.h>
using namespace std;
 
// function to find the position of the Most
// Significant Bit
int msbPos(int n)
{
    int pos = 0;
    while (n != 0) {
        pos++;
 
        // keeps shifting bits to the right
        // until we are left with 0
        n = n >> 1;
    }
    return pos;
}
 
// function to return at which place Josephus
// should sit to avoid being killed
int josephify(int n)
{
    /* Getting the position of the Most Significant
        Bit(MSB). The leftmost '1'. If the number is
    '41' then its binary is '101001'.
        So msbPos(41) = 6 */
    int position = msbPos(n);
 
    /* 'j' stores the number with which to XOR the
        number 'n'. Since we need '100000'
    We will do 1<<6-1 to get '100000' */
    int j = 1 << (position - 1);
 
    /* Toggling the Most Significant Bit. Changing
    the leftmost '1' to '0'.
    101001 ^ 100000 = 001001 (9) */
    n = n ^ j;
 
    /* Left-shifting once to add an extra '0' to
        the right end of the binary number
        001001 = 010010 (18) */
    n = n << 1;
 
    /* Toggling the '0' at the end to '1' which
    is essentially the same as putting the
    MSB at the rightmost place. 010010 | 1
    = 010011 (19) */
    n = n | 1;
 
    return n;
}
 
// hard coded driver main function to run the program
int main()
{
    int n = 41;
    cout <<josephify(n);
    return 0;
}// This code is contributed by Mukul singh.

// C program for josephus problem
 
#include <stdio.h>
 
// function to find the position of the Most
// Significant Bit
int msbPos(int n)
{
    int pos = 0;
    while (n != 0) {
        pos++;
 
        // keeps shifting bits to the right
        // until we are left with 0
        n = n >> 1;
    }
    return pos;
}
 
// function to return at which place Josephus
// should sit to avoid being killed
int josephify(int n)
{
    /*  Getting the position of the Most Significant
        Bit(MSB). The leftmost '1'. If the number is
       '41' then its binary is '101001'.
        So msbPos(41) = 6   */
    int position = msbPos(n);
 
    /* 'j' stores the number with which to XOR the
        number 'n'. Since we need '100000'
       We will do 1<<6-1 to get '100000' */
    int j = 1 << (position - 1);
 
    /* Toggling the Most Significant Bit. Changing
       the leftmost '1' to '0'.
       101001 ^ 100000 = 001001 (9) */
    n = n ^ j;
 
    /*  Left-shifting once to add an extra '0' to
        the right end of the binary number
        001001 = 010010 (18) */
    n = n << 1;
 
    /* Toggling the '0' at the end to '1' which
       is essentially the same as putting the
       MSB at the rightmost place. 010010 | 1
       = 010011 (19) */
    n = n | 1;
 
    return n;
}
 
// hard coded driver main function to run the program
int main()
{
    int n = 41;
    printf("%d\n", josephify(n));
    return 0;
}

// Java program for josephus problem
 
public class GFG
{
    // method to find the position of the Most
    // Significant Bit
    static int msbPos(int n)
    {
        int pos = 0;
        while (n != 0) {
            pos++;
      
            // keeps shifting bits to the right
            // until we are left with 0
            n = n >> 1;
        }
        return pos;
    }
      
    // method to return at which place Josephus
    // should sit to avoid being killed
    static int josephify(int n)
    {
        /*  Getting the position of the Most Significant
            Bit(MSB). The leftmost '1'. If the number is
           '41' then its binary is '101001'.
            So msbPos(41) = 6   */
        int position = msbPos(n);
      
        /* 'j' stores the number with which to XOR the
            number 'n'. Since we need '100000'
           We will do 1<<6-1 to get '100000' */
        int j = 1 << (position - 1);
      
        /* Toggling the Most Significant Bit. Changing
           the leftmost '1' to '0'.
           101001 ^ 100000 = 001001 (9) */
        n = n ^ j;
      
        /*  Left-shifting once to add an extra '0' to
            the right end of the binary number
            001001 = 010010 (18) */
        n = n << 1;
      
        /* Toggling the '0' at the end to '1' which
           is essentially the same as putting the
           MSB at the rightmost place. 010010 | 1
           = 010011 (19) */
        n = n | 1;
      
        return n;
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        int n = 41;
        System.out.println(josephify(n));
    }
}

# Python3 program for josephus problem
 
# Function to find the position
# of the Most Significant Bit
def msbPos(n):
    pos = 0
    while n != 0:
        pos += 1
        n = n >> 1
    return pos
 
# Function to return at which
# place Josephus should sit to
# avoid being killed
def josephify(n):
     
    # Getting the position of the Most
    # Significant Bit(MSB). The leftmost '1'.
    # If the number is '41' then its binary
    # is '101001'. So msbPos(41) = 6
    position = msbPos(n)
 
    # 'j' stores the number with which to XOR 
    # the number 'n'. Since we need '100000'
    # We will do 1<<6-1 to get '100000'
    j = 1 << (position - 1)
 
    # Toggling the Most Significant Bit.
    # Changing the leftmost '1' to '0'.
    # 101001 ^ 100000 = 001001 (9)
    n = n ^ j
 
    # Left-shifting once to add an extra '0' 
    # to the right end of the binary number
    # 001001 = 010010 (18)
    n = n << 1
 
    # Toggling the '0' at the end to '1' 
    # which is essentially the same as
    # putting the MSB at the rightmost
    # place. 010010 | 1 = 010011 (19)
    n = n | 1
 
    return n
 
# Driver Code
n = 41
print (josephify(n))
 
# This code is contributed by Shreyanshi Arun.

// C# program for Josephus Problem
using System;
 
public class GFG
{
     
    // Method to find the position
    // of the Most Significant Bit
    static int msbPos(int n)
    {
        int pos = 0;
        while (n != 0) {
            pos++;
     
            // keeps shifting bits to the right
            // until we are left with 0
            n = n >> 1;
        }
        return pos;
    }
     
    // method to return at which place Josephus
    // should sit to avoid being killed
    static int josephify(int n)
    {
         
        // Getting the position of the Most Significant
        // Bit(MSB). The leftmost '1'. If the number is
        // '41' then its binary is '101001'.
        // So msbPos(41) = 6
        int position = msbPos(n);
     
        // 'j' stores the number with which to XOR 
        // the number 'n'. Since we need '100000'
        // We will do 1<<6-1 to get '100000'
        int j = 1 << (position - 1);
     
        // Toggling the Most Significant Bit.
        // Changing the leftmost '1' to '0'.
        // 101001 ^ 100000 = 001001 (9)
        n = n ^ j;
     
        // Left-shifting once to add an extra '0'
        // to the right end of the binary number
        // 001001 = 010010 (18)
        n = n << 1;
     
        // Toggling the '0' at the end to '1' which
        // is essentially the same as putting the
        // MSB at the rightmost place. 010010 | 1
        // = 010011 (19)
        n = n | 1;
     
        return n;
    }
     
    // Driver code
    public static void Main()
    {
        int n = 41;
        Console.WriteLine(josephify(n));
    }
}
 
// This code is contributed by vt_m .

<?php
// PHP program for josephus problem
 
// function to find the position of
// the Most Significant Bit
function msbPos($n)
{
    $pos = 0;
    while ($n != 0)
    {
        $pos++;
 
        // keeps shifting bits to the right
        // until we are left with 0
        $n = $n >> 1;
    }
    return $pos;
}
 
// function to return at which place Josephus
// should sit to avoid being killed
function josephify($n)
{
    /* Getting the position of the Most
       Significant Bit(MSB). The leftmost '1'.
       If the number is '41' then its binary
       is '101001'. So msbPos(41) = 6 */
    $position = msbPos($n);
 
    /* 'j' stores the number with which to
        XOR the number 'n'. Since we need
    '100000'. We will do 1<<6-1 to get '100000' */
    $j = 1 << ($position - 1);
 
    /* Toggling the Most Significant Bit.
    Changing the leftmost '1' to '0'.
    101001 ^ 100000 = 001001 (9) */
    $n = $n ^ $j;
 
    /* Left-shifting once to add an extra '0'
       to the right end of the binary number
       001001 = 010010 (18) */
    $n = $n << 1;
 
    /* Toggling the '0' at the end to '1' which
    is essentially the same as putting the
    MSB at the rightmost place. 010010 | 1
    = 010011 (19) */
    $n = $n | 1;
 
    return $n;
}
 
// Driver Code
$n = 41;
print(josephify($n));
 
// This code is contributed by mits
?>

<script>
 
// javascript program for josephus problem
 
// method to find the position of the Most
// Significant Bit
function msbPos(n)
{
    var pos = 0;
    while (n != 0) {
        pos++;
  
        // keeps shifting bits to the right
        // until we are left with 0
        n = n >> 1;
    }
    return pos;
}
  
// method to return at which place Josephus
// should sit to avoid being killed
function josephify(n)
{
    /*  Getting the position of the Most Significant
        Bit(MSB). The leftmost '1'. If the number is
       '41' then its binary is '101001'.
        So msbPos(41) = 6   */
    var position = msbPos(n);
  
    /* 'j' stores the number with which to XOR the
        number 'n'. Since we need '100000'
       We will do 1<<6-1 to get '100000' */
    var j = 1 << (position - 1);
  
    /* Toggling the Most Significant Bit. Changing
       the leftmost '1' to '0'.
       101001 ^ 100000 = 001001 (9) */
    n = n ^ j;
  
    /*  Left-shifting once to add an extra '0' to
        the right end of the binary number
        001001 = 010010 (18) */
    n = n << 1;
  
    /* Toggling the '0' at the end to '1' which
       is essentially the same as putting the
       MSB at the rightmost place. 010010 | 1
       = 010011 (19) */
    n = n | 1;
  
    return n;
}
 
// Driver Method
var n = 41;
document.write(josephify(n));
 
// This code is contributed by Amit Katiyar
</script>

Producción:  

19

Complejidad de tiempo: O(log n)
Complejidad de espacio: O(1)

Artículos anteriores sobre el mismo tema:  

1. problema de Josefo | Conjunto 1 (Solución AO(n))
2. problema de Josefo | Conjunto 2 (Una solución simple cuando k = 2)

Este artículo es una contribución de Palash Nigam . 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.