Рубрики

Числа, у которых побитовое ИЛИ и сумма с N равны

Для заданного неотрицательного целого числа N задача состоит в том, чтобы найти количество неотрицательных целых чисел
меньше или равно N, чье побитовое ИЛИ и сумма с N равны.
Примеры :

Input  : N = 3
Output : 1
0 is the only number in [0, 3]
that satisfies given property.
(0 + 3) = (0 | 3)

Input  : 10
Output : 4
(0 + 10) = (0 | 10) (Both are 10)
(1 + 10) = (1 | 10) (Both are 11)
(4 + 10) = (4 | 10) (Both are 14)
(5 + 10) = (5 | 10) (Both are 15)

Простое решение — перебрать все числа от 0 до N и выполнить побитовое ИЛИ и СУММУ с N, если оба равны счетчику приращений.
Временная сложность = O (N).

Эффективным решением является выполнение следующих шагов.
1. Найти счетчик нулевого бита в N.
2. Верните пау (2, количество).

Идея основана на том факте, что побитовое ИЛИ и сумма числа x с N равны, если и только если
побитовое И х с N будет равно 0

Let, N=10 =10102.
Bitwise AND of a number with N will be 0, if number 
contains zero bit with all respective set bit(s) of
N and either zero bit or set bit with all respective 
zero bit(s) of N (because, 0&0=1&0=0).
  e.g. 
bit     : 1   0   1   0
position: 4   3   2   1
Bitwise AND of any number with N will be 0, if the number
has following bit pattern
1st position can be  either 0 or 1 (2 ways)
2nd position can be  1 (1 way)
3rd position can be  either 0 or 1 (2 ways)
4th position can be  1 (1 way)
Total count = 2*1*2*1 = 22 = 4.

C ++

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

using namespace std;

  
// Функция для поиска всего 0 битов в числе

unsigned int CountZeroBit(int n)

{

    unsigned int count = 0;

    while(n)

    

       if (!(n & 1))

           count++;

       n >>= 1;

    }

    return count;

}

  
// Функция для поиска количества неотрицательных чисел
// меньше или равно N, чье побитовое ИЛИ и
// СУММА с N равны.

int CountORandSumEqual(int N )

{

    // подсчитываем количество нулевых бит в N

    int count = CountZeroBit(N);

  

    // сила 2 для подсчета

    return (1 << count);

}

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

int main()

{

   int N = 10;

   cout << CountORandSumEqual(N);

   return 0;

Джава

// Java-программа для подсчета чисел, чьи биты
// ИЛИ и сумма с N равна

class GFG {

      

    // Функция для поиска всего 0 битов в числе

    static int CountZeroBit(int n)

    {

        int count = 0;

          

        while(n > 0)

        

            if ((n & 1) != 0)

                count++;

                  

            n >>= 1;

        }

          

        return count;

    }

      

    // Функция для поиска неотрицательных значений

    // числа, меньшие или равные N, чьи

    // побитовое ИЛИ и СУММА с N равны.

    static int CountORandSumEqual(int N )

    {

          

        // подсчитываем количество нулевых бит в N

        int count = CountZeroBit(N);

      

        // сила 2 для подсчета

        return (1 << count);

    }

      

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

    public static void main (String[] args)

    {

          

        int N = 10;

          

        System.out.print(CountORandSumEqual(N));

    }

}

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

python3

# Python3 программа для подсчета чисел, чьи
# побитовое ИЛИ и сумма с N равны

  
# Функция для поиска всего 0 бит в числе

def CountZeroBit(n):

  

    count = 0

    while(n):

      

        if (not(n & 1)):

            count += 1

        n >>= 1

      

    return count

  
# Функция найти количество неотрицательных
# число меньше или равно N, чье
# побитовое ИЛИ и СУММА с N равны.

def CountORandSumEqual(N):

  

    # количество отсчетов нулевого бита в N

    count = CountZeroBit(N)

  

    # сила 2 для подсчета

    return (1 << count)

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

N = 10

print(CountORandSumEqual(N))

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для подсчета чисел, чьи
// побитовое ИЛИ и сумма с N равны

using System;

  

class GFG

{

      

    // Функция для поиска суммы

    // 0 бит в числе

    static int CountZeroBit(int n)

    {

        int count = 0;

        while(n>0)

        

            if (n%2!=0)

            count++;

            n >>= 1;

        }

        return count;

    }

   

    // Функция для поиска неотрицательных значений

    // числа, меньшие или равные N, чьи

    // побитовое ИЛИ и СУММА с N равны.

    static int CountORandSumEqual(int N )

    {

          

    // подсчитываем количество нулевых бит в N

    int count = CountZeroBit(N);

   

    // сила 2 для подсчета

    return (1 << count);

    }

      

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

    public static void Main()

    {

        int N = 10;

        Console.Write(CountORandSumEqual(N));

    }

}

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

PHP

<?php
// PHP-программа для подсчета
// числа, чьи побитовые
// ИЛИ и сумма с N равна

  
// Функция для поиска суммы
// 0 бит в числе

  

function CountZeroBit($n)

{

    $count = 0;

    while($n)

    

    if (!($n & 1))

        $count++;

    $n >>= 1;

    }

    return $count;

}

  
// Функция для поиска количества
// неотрицательные числа меньше
// чем или равно N, чье
// побитовое ИЛИ и СУММА с N
// равны.

  

function CountORandSumEqual($N )

{

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

    // нулевой бит в N

    $count = CountZeroBit($N);

  

    // сила 2 для подсчета

    return (1 << $count);

}

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

$N = 10;

echo CountORandSumEqual($N);

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


Выход :

 4

Общая временная сложность вышеуказанного решения будет O (log 2 (N)).

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

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

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

Числа, у которых побитовое ИЛИ и сумма с N равны

0.00 (0%) 0 votes