Рубрики

Программа для поиска паритета

Четность: четность числа относится к тому, содержит ли оно нечетное или четное число 1-бит. Число имеет «нечетную четность», если оно содержит нечетное число 1-бит, и является «четной четностью», если оно содержит четное число 1-бит.
Основная идея решения, приведенного ниже, заключается в том, что Loop при n не равен 0 и в цикле сбрасывает один из установленных битов и инвертирует четность.

Algorithm: getParity(n)
1. Initialize parity = 0
2. Loop while n != 0      
      a. Invert parity 
             parity = !parity
      b. Unset rightmost set bit
             n = n & (n-1)
3. return parity

Example:
 Initialize: n = 13 (1101)   parity = 0

n = 13 & 12  = 12 (1100)   parity = 1
n = 12 & 11 = 8  (1000)   parity = 0
n = 8 & 7 = 0  (0000)    parity = 1

Программа:

C ++

// C ++ программа для поиска паритета
// целого числа
# include<bits/stdc++.h>
# define bool int

using namespace std;

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

bool getParity(unsigned int n)

{

    bool parity = 0;

    while (n)

    {

        parity = !parity;

        n     = n & (n - 1);

    }     

    return parity;

}

  
/ * Драйверная программа для проверки getParity () * /

int main()

{

    unsigned int n = 7;

    cout<<"Parity of no "<<n<<" = "<<(getParity(n)? "odd": "even");

      

    getchar();

    return 0;

}

С

// C программа для поиска паритета
// целого числа
# include <stdio.h>
# define  bool int

  
/ * Функция для получения четности числа n. Возвращает 1

   если n имеет нечетную четность и возвращает 0, если n имеет четное

   паритет * /

bool getParity(unsigned int n)

{

    bool parity = 0;

    while (n)

    {

        parity = !parity;

        n      = n & (n - 1);

    }        

    return parity;

}

  
/ * Драйверная программа для проверки getParity () * /

int main()

{

    unsigned int n = 7;

    printf("Parity of no %d = %s",  n, 

             (getParity(n)? "odd": "even"));

      

    getchar();

    return 0;

}

Джава

// Java программа для поиска паритета
// целого числа

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.BigInteger;

  

class GFG

 {

    / * Функция для получения четности числа n.

    Возвращает 1, если n имеет нечетную четность, и

    возвращает 0, если n имеет четную четность * /

    static boolean getParity(int n)

    {

        boolean parity = false;

        while(n != 0)

        {

            parity = !parity;

            n = n & (n-1);

        }

        return parity;

          

    }

      

    / * Драйверная программа для проверки getParity () * /

    public static void main (String[] args)

    {

        int n = 12;

        System.out.println("Parity of no " + n + " = " +

                         (getParity(n)? "odd": "even")); 

    }

}

/ * Этот код предоставлен Amit khandelwal * / 

python3

# Python3 код для получения паритета.

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

def getParity( n ):

    parity = 0

    while n:

        parity = ~parity

        n = n & (n - 1)

    return parity

  
# Драйверная программа для проверки getParity ()

n = 7

print ("Parity of no ", n," = ",

     ( "odd" if getParity(n) else "even"))

  
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// C # программа для поиска четности целого числа

using System;

  

class GFG {

      

    / * Функция для получения четности числа n.

    Возвращает 1, если n имеет нечетную четность, и

    возвращает 0, если n имеет четную четность * /

    static bool getParity(int n)

    {

        bool parity = false;

        while(n != 0)

        {

            parity = !parity;

            n = n & (n-1);

        }

        return parity;

          

    }

      

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

    public static void Main ()

    {

        int n = 7;

        Console.Write("Parity of no " + n 

                 + " = " + (getParity(n)?

                          "odd": "even")); 

    }

}

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

PHP

<?php
// PHP программа для поиска паритета
// целого числа без знака

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

function getParity( $n)

{

    $parity = 0;

    while ($n)

    {

        $parity = !$parity;

        $n = $n & ($n - 1);

    

    return $parity;

}

  

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

    $n = 7;

    echo "Parity of no ",$n ," = "

          getParity($n)? "odd": "even";

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


Выход:

Parity of no 7 = odd

Выше решение может быть оптимизировано с помощью таблицы поиска. Пожалуйста, обратитесь к Bit Twiddle Hacks [1-е руководство] для деталей.

Сложность времени: время, затрачиваемое вышеуказанным алгоритмом, пропорционально количеству установленных битов. В худшем случае сложность O (Log n).

Использование: Четность используется в обнаружении ошибок и криптографии.

Вычислить четность числа, используя XOR и поиск по таблице

Ссылки:
http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive — последняя проверка 30 мая 2009 г.

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

Программа для поиска паритета

0.00 (0%) 0 votes