# Проверка делимости с помощью побитовых операции C++

Необходимо проверить делимость введенного пользователем числа на простые 3, 23, 107. При этом в программе нельзя использовать +, -, /, %. Признак делимости на 3 я нашел, на другие числа нет. Возможно есть какой-то общий признак делимости? Иначе как проверяется делимость в более низкоуровневых языках, где нет %?

посмотри на это: Как получить остаток от деления через битовые операции?

#include <stdio.h>

#include <stdint.h>

int subtract(uint32_t x, uint32_t y) {
// Iterate till there
// is no carry
while (y) {
// borrow contains common
// set bits of y and unset
// bits of x
uint32_t borrow = (~x) & y;

// Subtraction of bits of x
// and y where at least one
// of the bits is not set
x = x ^ y;

// Borrow is shifted by one
// so that subtracting it from
// x gives the required sum
y = borrow << 1;
}
return x;
}

uint32_t inc(uint32_t i) {
}
return i;
}

uint32_t divide(uint32_t n, uint32_t d) {
// n is dividend, d is divisor
// store the result in q: q = n / d
uint32_t q = 0;

// as long as the divisor fits into the remainder there is something to do
while (n >= d) {
uint32_t i = 0, d_t = d;
// determine to which power of two the divisor still fits the dividend
//
// i.e.: we intend to subtract the divisor multiplied by powers of two
// which in turn gives us a one in the binary representation
// of the result
while (n >= (d_t << 1)) {
i = inc(i);
d_t <<= 1;
}
// set the corresponding bit in the result
q |= 1 << i;
// subtract the multiple of the divisor to be left with the remainder
n = subtract(n, d_t);
// repeat until the divisor does not fit into the remainder anymore
}
return q;
}

int add(uint32_t x, uint32_t y) {
// Iterate till there is no carry
while (y) {
// carry now contains common set bits of x and y
uint32_t carry = x & y;

// Sum of bits of x and y where at least one of the bits is not set
x = x ^ y;

// Carry is shifted by one so that adding it to x gives the required sum
y = carry << 1;
}
return x;
}

uint32_t multiply(uint32_t a, uint32_t b) {
uint32_t result = 0;
while (b) // Iterate the loop till b==0
{
if (b & 01) // Bitwise &  of the value of b with 01
{
result = add(result, a); // Add a to result if b is odd .
}
a <<= 1; // Left shifting the value contained in 'a' by 1
// multiplies a by 2 for each loop
b >>= 1; // Right shifting the value contained in 'b' by 1.
}
return result;
}

uint32_t mod(uint32_t a, uint32_t b) {
uint32_t r = divide(a, b); // truncated division
return subtract(a, multiply(r, b));
}

int main(void) {
printf("%un", mod(33, 31));
return 0;
}


Answered by Pudge And Math on February 5, 2021

## Related Questions

### Как можно проще сделать сравнение, на месте * может быть любое число?operation_code типа string

0  Asked on January 3, 2021

### Как добавть прогрессбар при загрузке файла на Яндекс.Диск в C#

0  Asked on January 3, 2021

### в OpenCart после активации SeoPro не работает главная страница

1  Asked on January 3, 2021 by zim

### Real time Laravel

0  Asked on January 2, 2021 by htmlprogrammer

### Vk bot как среагировать на вступление в беседу?

1  Asked on January 2, 2021 by classic_fungus

### Настройка платежей на корпоративном аккаунте PayPal

0  Asked on January 2, 2021 by slava

### Как убрать результаты работы анимации при повторном запуске анимации?

2  Asked on January 2, 2021

### Необходимо вывести 111, а программа выводит [‘1’, ‘1’, ‘1’]

3  Asked on January 1, 2021

### Как сделать необычное выпадающее мегаменю?

1  Asked on January 1, 2021 by cheizer

### Как анимировать Skeleton Screen с помощью маски CSS?

2  Asked on January 1, 2021

### Почему не запускается Ubuntu и как пофиксить?

0  Asked on January 1, 2021

### как сделать объект в объекте

2  Asked on January 1, 2021

### ERROR TypeError: platformFormService.getTaskCandidateGroupId is not a function

1  Asked on January 1, 2021

### laravel проблемы с “a foreign key constraint fails”

3  Asked on January 1, 2021 by rizone

### Ошибка работы бота

1  Asked on January 1, 2021 by alexsn2020

### Internal Server Error 500 Postman

1  Asked on January 1, 2021 by blacit

### Как получить данные об авторизованном пользователе Yii в Websocket?

0  Asked on January 1, 2021 by cr1gger

### Не удается применить индексирование через [] к выражения типа int

1  Asked on December 31, 2020

### Ошибка java.lang.UnsatisfiedLinkError: no gdalalljni in java.library.path с GDAL на MacOS

0  Asked on December 31, 2020 by filislav

### for await, 2 варианта. Одно ли это и тоже?

1  Asked on December 31, 2020 by lasna1