Рубрики

Следующее большее число с тем же количеством установленных бит

Учитывая число x, найдите следующее число с таким же числом 1 бит в его двоичном представлении.

Например, рассмотрим x = 12, двоичное представление которого равно 1100 (исключая ведущие нули на 32-битной машине). Он содержит два логических 1 бита. Следующее большее число с двумя логическими 1 битами равно 17 (10001 2 ).

Алгоритм:

Когда мы наблюдаем двоичную последовательность от 0 до 2 n — 1 (n — количество битов), самые правые биты (наименее значимые) изменяются быстрее, чем левые большинство битов. Идея состоит в том, чтобы найти самую правую строку из 1 в х и сместить шаблон в крайнее правое положение, за исключением самого левого бита в шаблоне. Сдвиньте самый левый бит в шаблоне (пропущенный бит) на левую часть x на одну позицию. Пример проясняет это,

x = 156

10

x = 10011100

(2)

10011100
00011100 - right most string of 1's in x
00000011 - right shifted pattern except left most bit ------> [A]
00010000 - isolated left most bit of right most 1's pattern
00100000 - shiftleft-ed the isolated bit by one position ------> [B]
10000000 - left part of x, excluding right most 1's pattern ------> [C]
10100000 - add B and C (OR operation) ------> [D]
10100011 - add A and D which is required number 163

(10)

После практики с несколькими примерами это легко понять. Используйте приведенную ниже программу для генерации большего количества наборов.

Дизайн программы:

Нам нужно отметить несколько фактов двоичных чисел. Выражение x & -x выделит самый правый установленный бит в x (гарантируя, что x будет использовать форму дополнения 2 для отрицательных чисел). Если мы добавим результат к x, самая правая строка из 1 в x будет сброшена, и будет установлено непосредственное «0» слева от этого шаблона из 1, что является частью [B] объяснения выше. Например, если x = 156, x & -x приведет к 00000100, добавление этого результата к x приведет к 10100000 (см. Часть D). Мы ушли с правой сдвигающейся частью шаблона 1 (часть A вышеприведенного объяснения).

Есть разные способы достижения части А. Сдвиг вправо — это, по сути, операция деления. Каким должен быть наш делитель? Ясно, что оно должно быть кратным 2 (избегать ошибки 0,5 при смещении вправо), и оно должно смещать правый крайний шаблон 1 в крайнее правое положение. Выражение (x & -x) послужит цели делителя. Операция EX-OR между числом X и выражением, которое используется для сброса большинства правых битов, изолирует шаблон самой правой единицы.

Поправочный коэффициент:

Обратите внимание, что мы добавляем самый правый установленный бит в битовую комбинацию. Операция сложения вызывает смещение битовых позиций. Вес двоичной системы равен 2, один сдвиг вызывает увеличение в 2 раза. Поскольку увеличенное число ( rightOnesPattern в коде) используется дважды, ошибка распространяется дважды. Ошибка должна быть исправлена. Сдвиг вправо на 2 позиции исправит результат.

Популярное название для этой программы с Ame п умбра о л оного б ИТСА.

C ++

#include<iostream>

  

using namespace std;

  

typedef unsigned int uint_t;

  
// эта функция возвращает следующее большее число с тем же числом битов, что и x.
uint_t snoob(uint_t x)
{

  

  uint_t rightOne;

  uint_t nextHigherOneBit;

  uint_t rightOnesPattern;

  

  uint_t next = 0;

  

  if(x)

  {

  

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

    rightOne = x & -(signed)x;

  

    // сбросить паттерн и установить следующий старший бит

    // левая часть x будет здесь

    nextHigherOneBit = x + rightOne;

  

    // nextHigherOneBit теперь является частью [D] вышеприведенного объяснения.

  

    // изолировать шаблон

    rightOnesPattern = x ^ nextHigherOneBit;

  

    // правильная настройка шаблона

    rightOnesPattern = (rightOnesPattern)/rightOne;

  

    // поправочный коэффициент

    rightOnesPattern >>= 2;

  

    // rightOnesPattern теперь является частью [A] вышеприведенного объяснения.

  

    // интегрируем новый шаблон (Добавить [D] и [A])

    next = nextHigherOneBit | rightOnesPattern;

  }

  

  return next;

}

  

int main()

{

  int x = 156;

  cout<<"Next higher number with same number of set bits is "<<snoob(x);

  

  getchar();

  return 0;

}

Джава

// Реализация Java на вышеуказанном подходе

class GFG

{

      
// эта функция возвращает следующий выше
// число с таким же количеством битов, что и x.

static int snoob(int x)

{

  

int rightOne, nextHigherOneBit, rightOnesPattern, next = 0;

  

if(x > 0)

{

  

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

    rightOne = x & -x;

  

    // сбросить паттерн и установить следующий старший бит

    // левая часть x будет здесь

    nextHigherOneBit = x + rightOne;

  

    // nextHigherOneBit теперь является частью [D] вышеприведенного объяснения.

  

    // изолировать шаблон

    rightOnesPattern = x ^ nextHigherOneBit;

  

    // правильная настройка шаблона

    rightOnesPattern = (rightOnesPattern)/rightOne;

  

    // поправочный коэффициент

    rightOnesPattern >>= 2;

  

    // rightOnesPattern теперь является частью [A] вышеприведенного объяснения.

  

    // интегрируем новый шаблон (Добавить [D] и [A])

    next = nextHigherOneBit | rightOnesPattern;

}

  

return next;

}

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

public static void main (String[] args) 

{

    int x = 156;

    System.out.println("Next higher number with same" +

                    "number of set bits is "+snoob(x));

}
}

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

Python 3

# Эта функция возвращает следующее
# большее число с тем же
# количество битов, установленных как x.

def snoob(x):

      

    next = 0

    if(x):

          

        # самый правый установленный бит

        rightOne = x & -(x)

          

        # сбросить шаблон и

        # установить следующий более высокий бит

        # левая часть x будет

        # будь здесь

        nextHigherOneBit = x + int(rightOne)

          

        # nextHigherOneBit is

        # теперь часть [D] из

        # выше объяснение.

        # изолировать шаблон

        rightOnesPattern = x ^ int(nextHigherOneBit)

          

        # Правильно настроить шаблон

        rightOnesPattern = (int(rightOnesPattern) / 

                            int(rightOne))

          

        # поправочный коэффициент

        rightOnesPattern = int(rightOnesPattern) >> 2

          

        # rightOnesPattern теперь часть

        # [A] вышеприведенного объяснения.

          

        # интегрировать новый шаблон

        # (Добавить [D] и [A])

        next = nextHigherOneBit | rightOnesPattern

    return next

  
Код водителя

x = 156

print("Next higher number with " + 

      "same number of set bits is"

                          snoob(x))

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

C #

// C # Реализация на подходе выше

using System;

class GFG

{

      
// эта функция возвращает следующий выше
// число с таким же количеством битов, что и x.

static int snoob(int x)

{

  

    int rightOne, nextHigherOneBit, 

        rightOnesPattern, next = 0;

      

    if(x > 0)

    {

      

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

        rightOne = x & -x;

      

        // сбросить паттерн и установить следующий старший бит

        // левая часть x будет здесь

        nextHigherOneBit = x + rightOne;

      

        // nextHigherOneBit теперь является частью [D]

        // приведенного выше объяснения.

      

        // изолировать шаблон

        rightOnesPattern = x ^ nextHigherOneBit;

      

        // правильная настройка шаблона

        rightOnesPattern = (rightOnesPattern) / rightOne;

      

        // поправочный коэффициент

        rightOnesPattern >>= 2;

      

        // rightOnesPattern теперь является частью [A]

        // приведенного выше объяснения.

      

        // интегрируем новый шаблон (Добавить [D] и [A])

        next = nextHigherOneBit | rightOnesPattern;

    }

    return next;

}

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

static void Main() 

{

    int x = 156;

    Console.WriteLine("Next higher number with same" +

                      "number of set bits is " + snoob(x));

}
}

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

PHP

<?php 

  
// Эта функция возвращает следующее большее число
// с тем же количеством битов, что и x.

function snoob($x)

{

    $next = 0;

      

    if($x)

    {

      

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

        $rightOne = $x & - $x;

      

        // сбросить шаблон и установить следующий выше

        // левая часть x будет здесь

        $nextHigherOneBit = $x + $rightOne;

      

        // nextHigherOneBit теперь является частью [D] из

        // вышеприведенное объяснение.

      

        // изолировать шаблон

        $rightOnesPattern = $x ^ $nextHigherOneBit;

      

        // правильная настройка шаблона

        $rightOnesPattern = intval(($rightOnesPattern) / 

                                            $rightOne);

      

        // поправочный коэффициент

        $rightOnesPattern >>= 2;

      

        // rightOnesPattern теперь является частью [A]

        // приведенного выше объяснения.

      

        // интегрируем новый шаблон (Добавить [D] и [A])

        $next = $nextHigherOneBit | $rightOnesPattern;

    }

  

    return $next;

}

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

$x = 156;

echo "Next higher number with same "

     "number of set bits is " . snoob($x);

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


Выход:

Next higher number with same number of set bits is 163

Использование: Поиск / Генерация подмножеств.

Варианты:

  1. Напишите программу, чтобы найти число, которое сразу же меньше заданного, с таким же количеством логических 1 бит? (Довольно просто)
  2. Как посчитать или сгенерировать подмножества, доступные в данном наборе?

Ссылки:

  1. Хорошая презентация здесь .
  2. Hackers Delight by Warren (отличная и короткая книга о различных алгоритмах битовой магии, обязательная для энтузиастов)
  3. Справочное руководство CA от Harbison and Steele (Хорошая книга по стандарту C, вы можете получить доступ к кодовой части этого поста здесь ).

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

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

Следующее большее число с тем же количеством установленных бит

0.00 (0%) 0 votes