Рубрики

Проверьте, имеет ли число битов число последовательных установленных битов в порядке возрастания

Учитывая целое число n> 0, задача состоит в том, чтобы найти, увеличивается ли в битовой комбинации число целых чисел непрерывных 1 слева направо.
Примеры :

Input:19
Output:Yes
Explanation: Bit-pattern of 19 = 10011,
Counts of continuous 1's from left to right 
are 1, 2 which are in increasing order.

Input  : 183
Output : yes
Explanation: Bit-pattern of 183 = 10110111,
Counts of continuous 1's from left to right 
are 1, 2, 3 which are in increasing order.

Простое решение — сохранить двоичное представление заданного числа в строку, затем пройти слева направо и посчитать количество непрерывных единиц. Для каждого совпадения с 0 проверяйте значение предыдущего счетчика непрерывных 1 на текущее значение, если значение предыдущего счетчика больше, чем значение текущего счетчика, тогда возвращайте False, иначе, когда строка заканчивается, возвращают True.

C ++

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

using namespace std;

  
// Возвращает true, если n имеет увеличивающееся количество
// Непрерывно-1 иначе ложь

bool findContinuous1(int n)

{

    const int bits = 8*sizeof(int);

  

    // сохранить битовый массив n в

    // бит-бит-бит

    string bp = bitset <bits>(n).to_string();

  

    // устанавливаем prev_count = 0 и curr_count = 0.

    int prev_count = 0, curr_count = 0;

  

    int i = 0;

    while (i < bits)

    {

        if (bp[i] == '1')

        {

            // увеличиваем текущий счетчик непрерывных -1

            curr_count++;

            i++;

        }

  

        // пройти все непрерывно-0

        else if (bp[i-1] == '0')

        {

            i++;

            curr_count = 0;

            continue;

        }

  

        // проверяем prev_count и curr_count

        // при встрече первого нуля после

        // непрерывный-1с

        else

        {

            if (curr_count < prev_count)

                return 0;

            i++;

            prev_count=curr_count;

            curr_count = 0;

        }

    }

  

    // проверка последней последовательности непрерывного -1

    if (prev_count > curr_count && (curr_count != 0))

        return 0;

  

    return 1;

}

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

int main()

{

    int n = 179;

    if (findContinuous1(n))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}

Выход :

Yes

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

Ниже приведена реализация.

C ++

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

using namespace std;

  
// Возвращает true, если n имеет количество последовательных
// 1 увеличивают порядок.

bool areSetBitsIncreasing(int n)

{

    // Инициализируем предыдущий счет

    int prev_count = INT_MAX;

  

    // Мы проходим биты справа налево

    // и проверяем, уменьшается ли количество

    // заказ.

    while (n > 0)

    {

        // Игнорируем 0, пока мы не достигнем установленного бита.

        while (n > 0 && n % 2 == 0)

           n = n/2;

  

        // Считаем текущие установленные биты

        int curr_count = 1;

        while (n > 0 && n % 2 == 1)

        {

            n = n/2;

            curr_count++;

        }

  

        // Сравнить текущий с предыдущим и

        // обновить предыдущее.

        if (curr_count >= prev_count)

            return false;

        prev_count = curr_count;

    }

  

    return true;

}

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

int main()

{

    int n = 10;

    if (areSetBitsIncreasing(n))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}

Джава

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

import java .io.*;

  

class GFG {

      

    // Возвращает true, если n имеет количество

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

    // заказ.

    static boolean areSetBitsIncreasing(int n)

    {

          

        // Инициализируем предыдущий счет

        int prev_count = Integer.MAX_VALUE;

      

        // Мы проходим биты справа

        // оставляем и проверяем, если счет

        // убывающий порядок.

        while (n > 0)

        {

              

            // Игнорируем 0, пока мы не достигнем

            // установленный бит

            while (n > 0 && n % 2 == 0)

            n = n/2;

      

            // Считаем текущие установленные биты

            int curr_count = 1;

            while (n > 0 && n % 2 == 1)

            {

                n = n/2;

                curr_count++;

            }

      

            // Сравнить текущий с предыдущим

            // и обновить предыдущее.

            if (curr_count >= prev_count)

                return false;

            prev_count = curr_count;

        }

      

        return true;

    }

      

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

    static public void main (String[] args)

    {

        int n = 10;

          

        if (areSetBitsIncreasing(n))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

  
// Этот код предоставлен anuj_67.

Python 3

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

  

import sys

  
# Возвращает true, если n имеет количество
# последовательные 1 увеличивают порядок.

def areSetBitsIncreasing(n):

  

    # Инициализировать предыдущий счет

    prev_count = sys.maxsize

  

    # Мы проходим биты справа

    # осталось и проверьте, если счет

    # убывающий порядок.

    while (n > 0):

      

        # Игнорировать 0, пока мы не достигнем

        # установить бит.

        while (n > 0 and n % 2 == 0):

            n = int(n/2)

  

        # Количество текущих установленных битов

        curr_count = 1

        while (n > 0 and n % 2 == 1):

          

            n = n/2

            curr_count += 1

          

        # Сравнить текущий с предыдущим

        # и обновить предыдущее.

        if (curr_count >= prev_count):

            return False

        prev_count = curr_count

  

    return True

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

n = 10

  

if (areSetBitsIncreasing(n)):

    print("Yes")

else:

    print("No")

      
# Этот код предоставлен Smitha

C #

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

using System;

  

class GFG {

      

    // Возвращает true, если n имеет количество

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

    // заказ.

    static bool areSetBitsIncreasing(int n)

    {

          

        // Инициализируем предыдущий счет

        int prev_count = int.MaxValue;

      

        // Мы проходим биты справа

        // оставляем и проверяем, если счет

        // убывающий порядок.

        while (n > 0)

        {

              

            // Игнорируем 0, пока мы не достигнем

            // установленный бит

            while (n > 0 && n % 2 == 0)

            n = n/2;

      

            // Считаем текущие установленные биты

            int curr_count = 1;

            while (n > 0 && n % 2 == 1)

            {

                n = n/2;

                curr_count++;

            }

      

            // Сравнить текущий с предыдущим

            // и обновить предыдущее.

            if (curr_count >= prev_count)

                return false;

            prev_count = curr_count;

        }

      

        return true;

    }

      

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

    static public void Main ()

    {

        int n = 10;

          

        if (areSetBitsIncreasing(n))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

}

  
// Этот код предоставлен anuj_67.

PHP

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

  
// Возвращает true, если n имеет
// количество последовательных
// 1 увеличивают порядок.

function areSetBitsIncreasing( $n)

{

    // Инициализируем предыдущий счет

    $prev_count = PHP_INT_MAX;

  

    // Мы проходим биты справа

    // влево и проверить, считается ли

    // убывает порядок.

    while ($n > 0)

    {

        // игнорируем 0, пока мы

        // достичь установленного бита.

        while ($n > 0 && $n % 2 == 0)

        $n = $n / 2;

  

        // Считаем текущие установленные биты

        $curr_count = 1;

        while ($n > 0 and $n % 2 == 1)

        {

            $n = $n / 2;

            $curr_count++;

        }

  

        // Сравнить текущий с предыдущим

        // и обновить предыдущее.

        if ($curr_count >= $prev_count)

            return false;

        $prev_count = $curr_count;

    }

  

    return true;

}

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

$n = 10;

if (areSetBitsIncreasing($n))

    echo "Yes";

else

    echo "No";

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

Выход :

No

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

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

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

Проверьте, имеет ли число битов число последовательных установленных битов в порядке возрастания

0.00 (0%) 0 votes