Рубрики

Длина самой длинной последовательной единицы в двоичном представлении

Учитывая число n, найдите длину самых длинных последовательных 1s в его двоичном представлении.

Примеры :

Input : n = 14
Output : 3
The binary representation of 14 is 1110.

Input : n = 222
Output : 4
The binary representation of 222 is 11011110.

Наивный подход. Одним простым способом было бы просто зациклить биты и отслеживать количество последовательных установленных битов и максимум, которого достигло это значение. При таком подходе нам нужно преобразовать его в двоичное представление (base-2), а затем найти и распечатать результат.

Использование Bit Magic: Идея основана на концепции, что если мы И битовая последовательность со сдвинутой версией самого себя, мы эффективно удаляем завершающий 1 из каждой последовательности последовательных 1.

      11101111   (x)
    & 11011110   (x << 1)
    ----------
      11001110   (x & (x << 1)) 
        ^    ^
        |    |
   trailing 1 removed

Таким образом, операция x = (x & (x << 1)) уменьшает длину каждой последовательности 1s на единицу в двоичном представлении x. Если мы продолжим выполнять эту операцию в цикле, мы получим x = 0. Количество итераций, необходимых для достижения 0, на самом деле является длиной самой длинной последовательной последовательности 1 с.

C ++

// C ++ программа для определения длины самого длинного
// последовательные 1 в двоичном представлении
// число.
#include<bits/stdc++.h>

using namespace std;

  

int maxConsecutiveOnes(int x)

{

    // Инициализировать результат

    int count = 0;

  

    // Подсчитать количество итераций до

    // достичь х = 0.

    while (x!=0)

    {

        // Эта операция уменьшает длину

        // каждой последовательности 1 с по одному.

        x = (x & (x << 1));

  

        count++;

    }

  

    return count;

}

  
// Код драйвера

int main()

{

    cout << maxConsecutiveOnes(14) << endl;

    cout << maxConsecutiveOnes(222) << endl;

    return 0;

}

Джава

// Java-программа для определения длины самого длинного
// последовательные 1 в двоичном представлении
// число.

class MaxConsecutiveOnes

{

    private static int maxConsecutiveOnes(int x)

    {

        // Инициализировать результат

        int count = 0;

  

        // Подсчитать количество итераций до

        // достичь х = 0.

        while (x!=0)

        {

            // Эта операция уменьшает длину

            // каждой последовательности 1 с по одному.

            x = (x & (x << 1));

  

            count++;

        }

  

        return count;

    }

  

    // Код драйвера

    public static void main(String strings[])

    {

        System.out.println(maxConsecutiveOnes(14));

        System.out.println(maxConsecutiveOnes(222));

    }

}

python3

# Python программа для поиска
# длина самого длинного
# последовательных 1 в
# двоичное представление
# число.

  

def maxConsecutiveOnes(x):

  

    # Инициализировать результат

    count = 0

   

    # Подсчитать количество итераций до

    # достичь х = 0.

    while (x!=0):

      

        # Эта операция уменьшает длину

        # каждой последовательности 1 с по одному.

        x = (x & (x << 1))

   

        count=count+1

      

    return count

  
# Код драйвера

  

print(maxConsecutiveOnes(14))

print(maxConsecutiveOnes(222))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для определения длины
// самые длинные последовательные 1 в двоичном
// представление числа.

using System;

  

class GFG {

      

    // Функция для определения длины

    // самые длинные последовательные 1 в двоичном

    // представление числа

    private static int maxConsecutiveOnes(int x)

    {

          

        // Инициализировать результат

        int count = 0;

  

        // Подсчитать количество итераций

        // достичь х = 0.

        while (x != 0)

        {

              

            // Эта операция уменьшает длину

            // каждой последовательности 1 с по одному.

            x = (x & (x << 1));

  

            count++;

        }

  

        return count;

    }

  

    // Код драйвера

    public static void Main()

    {

        Console.WriteLine(maxConsecutiveOnes(14));

        Console.Write(maxConsecutiveOnes(222));

    }

}

  
// Этот код предоставлен Нитином Митталом.

PHP

<?php
// PHP программа для определения длины
// самого длинного подряд
// 1 в двоичном представлении
// число.

  

function maxConsecutiveOnes($x)

{

    // Инициализировать результат

    $count = 0;

  

    // Подсчитать количество

    // итерации для достижения х = 0.

    while ($x != 0)

    {

        // Эта операция уменьшает

        // длина каждой последовательности

        // из 1 по одному.

        $x = ($x & ($x << 1));

  

        $count++;

    }

  

    return $count;

}

  
// Код драйвера

echo maxConsecutiveOnes(14), "\n";

echo maxConsecutiveOnes(222), "\n";

  
// Этот код предоставлен Ajit
?>


Выход :

3
4

Эта статья предоставлена Панкаджем Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Длина самой длинной последовательной единицы в двоичном представлении

0.00 (0%) 0 votes