Posición del bit K-th set en un número

Dados dos números N y K , la tarea es encontrar el índice del K-ésimo conjunto de bits en el número de la derecha. 
Nota : La indexación en la representación binaria comienza desde 0 desde la derecha. Por ejemplo, en el número binario «000011», el primer bit establecido está en el índice 0 desde la derecha y el segundo bit establecido está en el índice 1 desde la derecha.
Ejemplos: 
 

Input: N = 15, K = 3
Output: 2
15 is "1111", hence the third bit is at index 2 from right. 

Input:  N = 19, K = 2
Output: 1
19 is "10011", hence the second set bit is at index 1 from right. 

Enfoque: Inicialice un contador 0 y auméntelo si el último bit está establecido en el número. Para acceder al siguiente bit, desplaza el número a la derecha en 1. Cuando el valor del contador es igual a K, devolvemos el índice del número que se incrementaba en cada desplazamiento a la derecha. 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the Kth set bit
int FindIndexKthBit(int n, int k)
{
    int cnt = 0;
    int ind = 0;
 
    // Traverse in the binary
    while (n) {
 
        // Check if the last
        // bit is set or not
        if (n & 1)
            cnt++;
 
        // Check if count is equal to k
        // then return the index
        if (cnt == k)
            return ind;
 
        // Increase the index
        // as we move right
        ind++;
 
        // Right shift the number by 1
        n = n >> 1;
    }
 
    return -1;
}
 
// Driver Code
int main()
{
    int n = 15, k = 3;
    int ans = FindIndexKthBit(n, k);
    if (ans != -1)
        cout << ans;
    else
        cout << "No k-th set bit";
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG
{
 
// Function that returns the Kth set bit
static int FindIndexKthBit(int n, int k)
{
    int cnt = 0;
    int ind = 0;
 
    // Traverse in the binary
    while (n > 0)
    {
 
        // Check if the last
        // bit is set or not
        if ((n & 1 ) != 0)
            cnt++;
 
        // Check if count is equal to k
        // then return the index
        if (cnt == k)
            return ind;
 
        // Increase the index
        // as we move right
        ind++;
 
        // Right shift the number by 1
        n = n >> 1;
    }
 
    return -1;
}
 
// Driver Code
public static void main(String args[])
{
    int n = 15, k = 3;
    int ans = FindIndexKthBit(n, k);
    if (ans != -1)
        System.out.println(ans);
    else
        System.out.println("No k-th set bit");
}
}
 
// This code is contributed by
// Surendra_Gangwar

Python3

# Python3 implementation of the approach
 
# Function that returns the Kth set bit
def FindIndexKthBit(n, k):
 
    cnt, ind = 0, 0
     
    # Traverse in the binary
    while n > 0:
 
        # Check if the last
        # bit is set or not
        if n & 1:
            cnt += 1
 
        # Check if count is equal to k
        # then return the index
        if cnt == k:
            return ind
 
        # Increase the index
        # as we move right
        ind += 1
 
        # Right shift the number by 1
        n = n >> 1
     
    return -1
 
# Driver Code
if __name__ == "__main__":
 
    n, k = 15, 3
    ans = FindIndexKthBit(n, k)
     
    if ans != -1:
        print(ans)
    else:
        print("No k-th set bit")
         
# This code is contributed by
# Rituraj Jain

C#

// C# program to implement
// the above approach
using System;
 
class GFG
{
 
// Function that returns the Kth set bit
static int FindIndexKthBit(int n, int k)
{
    int cnt = 0;
    int ind = 0;
 
    // Traverse in the binary
    while (n > 0)
    {
 
        // Check if the last
        // bit is set or not
        if ((n & 1 ) != 0)
            cnt++;
 
        // Check if count is equal to k
        // then return the index
        if (cnt == k)
            return ind;
 
        // Increase the index
        // as we move right
        ind++;
 
        // Right shift the number by 1
        n = n >> 1;
    }
 
    return -1;
}
 
// Driver Code
public static void Main()
{
    int n = 15, k = 3;
    int ans = FindIndexKthBit(n, k);
    if (ans != -1)
        Console.WriteLine(ans);
    else
        Console.WriteLine("No k-th set bit");
}
}
 
// This code is contributed by
// Code_Mech.

PHP

<?php
// PHP program to implement
// the above approach
 
// Function that returns the Kth set bit
function FindIndexKthBit($n, $k)
{
    $cnt = 0;
    $ind = 0;
 
    // Traverse in the binary
    while ($n)
    {
 
        // Check if the last
        // bit is set or not
        if ($n & 1)
            $cnt++;
 
        // Check if count is equal to k
        // then return the index
        if ($cnt == $k)
            return $ind;
 
        // Increase the index
        // as we move right
        $ind++;
 
        // Right shift the number by 1
        $n = $n >> 1;
    }
 
    return -1;
}
 
// Driver Code
$n = 15;
$k = 3;
 
$ans = FindIndexKthBit($n, $k);
 
if ($ans != -1)
    echo $ans;
else
    echo "No k-th set bit";
 
// This code is contributed by Ryuga
?>

Javascript

<script>
    // Javascript program to implement
    // the above approach
     
    // Function that returns the Kth set bit
    function FindIndexKthBit(n, k)
    {
        let cnt = 0;
        let ind = 0;
 
        // Traverse in the binary
        while (n > 0) {
 
            // Check if the last
            // bit is set or not
            if (n & 1 > 0)
                cnt++;
 
            // Check if count is equal to k
            // then return the index
            if (cnt == k)
                return ind;
 
            // Increase the index
            // as we move right
            ind++;
 
            // Right shift the number by 1
            n = n >> 1;
        }
 
        return -1;
    }
     
    let n = 15, k = 3;
    let ans = FindIndexKthBit(n, k);
    if (ans != -1)
        document.write(ans);
    else
        document.write("No k-th set bit");
 
</script>
Producción: 

2

 

Complejidad de tiempo: O(logN), ya que estamos usando un bucle while para atravesar y en cada recorrido estamos desplazando N a la derecha en 1 lugar, lo que equivale a la división mínima de N entre 2. Por lo tanto, el tiempo efectivo será 1+1 /2+1/4+…..+1/2^N que es equivalente a logN.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

Artículo escrito por Striver 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 *