Рубрики

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

Немного магии

Учитывая число n, напишите функцию, которая возвращает true, если n делится на 9, иначе false. Самый простой способ проверить делимость n на 9 — это сделать n% 9.
Другой метод состоит в суммировании цифр n. Если сумма цифр кратна 9, то n кратна 9.
Вышеуказанные методы не являются побитовыми операторами и требуют использования% и /.
Побитовые операторы обычно быстрее, чем по модулю и операторам деления. Ниже приведен метод побитового оператора для проверки делимости на 9.

C ++

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

using namespace std;

  
// Битовая операторная функция для проверки делимости на 9

bool isDivBy9(int n)

{

    // Базовые случаи

    if (n == 0 || n == 9)

        return true;

    if (n < 9)

        return false;

  

    // Если n больше 9, то повторить для [floor (n / 9) - n% 8]

    return isDivBy9((int)(n >> 3) - (int)(n & 7));

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    // Напечатаем все кратные 9 от 0 до 100

    // используя вышеуказанный метод

    for (int i = 0; i < 100; i++)

        if (isDivBy9(i))

            cout << i << " ";

    return 0;

}

Джава

// Java-программа для проверки номера
// кратно 9 с использованием побитовых операторов

import java.lang.*;

  

class GFG {

  

    // Битовая операторная функция

    // проверить делимость на 9

    static boolean isDivBy9(int n)

    {

  

        // Базовые случаи

        if (n == 0 || n == 9)

            return true;

        if (n < 9)

            return false;

  

        // Если n больше 9, то

        // повторяем для [floor (n / 9) - n% 8]

        return isDivBy9((int)(n >> 3) - (int)(n & 7));

    }

  

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

    public static void main(String arg[])

    {

  

        // Напечатаем все кратные 9 из

        // от 0 до 100, используя вышеуказанный метод

        for (int i = 0; i < 100; i++)

            if (isDivBy9(i))

                System.out.print(i + " ");

    }

}

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

python3

# Битовый оператор на основе
# функция для проверки делимости на 9

  

def isDivBy9(n):

  

    # Базовые случаи

    if (n == 0 or n == 9):

        return True

    if (n < 9):

        return False

   

    # Если n больше 9,

    # затем повторить для [этаж (n / 9) - n% 8]

    return isDivBy9((int)(n>>3) - (int)(n&7))

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

  
# Давайте распечатать все кратные
№ 9 от 0 до 100
# используя вышеуказанный метод

for i in range(100):

    if (isDivBy9(i)):

        print(i, " ", end ="")

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

C #

// C # программа для проверки, если число
// кратно 9 с использованием побитовых операторов

using System;

  

class GFG {

  

    // Битовая операторная функция

    // проверить делимость на 9

    static bool isDivBy9(int n)

    {

        // Базовые случаи

        if (n == 0 || n == 9)

            return true;

        if (n < 9)

            return false;

  

        // Если n больше 9, то

        // повторяем для [floor (n / 9) - n% 8]

        return isDivBy9((int)(n >> 3) - (int)(n & 7));

    }

  

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

    public static void Main()

    {

        // Напечатаем все кратные 9 из

        // от 0 до 100, используя вышеуказанный метод

        for (int i = 0; i < 100; i++)

            if (isDivBy9(i))

                Console.Write(i + " ");

    }

}

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

PHP

<?php
// PHP программа для проверки номера
// кратно 9 с использованием побитового
// операторы

  
// Битовая операторная функция
// проверить делимость на 9

function isDivBy9($n)

{

      

    // Базовые случаи

    if ($n == 0 || $n == 9)

        return true;

    if ($n < 9)

        return false;

  

    // Если n больше 9,

    // затем повторяем для [floor (n / 9) -

    // n% 8]

    return isDivBy9(($n >> 3) - 

                    ($n & 7));

}

  

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

    // Давайте напечатаем все кратные

    // из 9 от 0 до 100

    // используя вышеуказанный метод

    for ($i = 0; $i < 100; $i++)

        if (isDivBy9($i))

            echo $i ," ";

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


Выход:

0 9 18 27 36 45 54 63 72 81 90 99

Как это работает?
n / 9 можно записать в терминах n / 8, используя следующую простую формулу.

n/9 = n/8 - n/72

Поскольку нам нужно использовать побитовые операторы, мы получаем значение floor (n / 8), используя n >> 3, и получаем значение n% 8, используя n & 7 . Нам нужно написать вышеприведенное выражение в терминах floor (n / 8) и n% 8 .
n / 8 равно «Этаж (n / 8) + (n% 8) / 8» . Запишем приведенное выше выражение в терминах floor (n / 8) и n% 8

n/9 = floor(n/8) + (n%8)/8 - [floor(n/8) + (n%8)/8]/9
n/9 = floor(n/8) - [floor(n/8) - 9(n%8)/8 + (n%8)/8]/9
n/9 = floor(n/8) - [floor(n/8) - n%8]/9

Из приведенного выше уравнения n кратно 9, только если выражение floor (n / 8) — [floor (n / 8) — n% 8] / 9 является целым числом. Это выражение может быть только целым числом, если подвыражение [floor (n / 8) — n% 8] / 9 является целым числом. Подвыражение может быть только целым числом, если [floor (n / 8) — n% 8] кратно 9 . Таким образом, проблема сводится к меньшему значению, которое можно записать в терминах побитовых операторов.

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

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

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

0.00 (0%) 0 votes