Разделите число на 3 без использования операторов *, /, +, -, %.
https://stackoverflow.com//questions/11694546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Как бы вы разделили число на 3, не используя *, /, +, -, %, операторы?
Число может быть подписанным или беззнаковым.
Решение
Это простая функция который выполняет желаемую операцию.Но для этого требуется + оператор, поэтому все, что вам осталось сделать, это сложить значения с помощью битовых операторов:
// replaces the + operator
int add(int x, int y)
{
while (x) {
int t = (x & y) << 1;
y ^= x;
x = t;
}
return y;
}
int divideby3(int num)
{
int sum = 0;
while (num > 3) {
sum = add(num >> 2, sum);
num = add(num >> 2, num & 3);
}
if (num == 3)
sum = add(sum, 1);
return sum;
}
Как прокомментировал Джим, это работает, потому что:
n = 4 * a + bn / 3 = a + (a + b) / 3Так
sum += a,n = a + b, и повторяемКогда
a == 0 (n < 4),sum += floor(n / 3);то есть1,if n == 3, else 0
Другие советы
Идиотские условия требуют идиотского решения:
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE * fp=fopen("temp.dat","w+b");
int number=12346;
int divisor=3;
char * buf = calloc(number,1);
fwrite(buf,number,1,fp);
rewind(fp);
int result=fread(buf,divisor,number,fp);
printf("%d / %d = %d", number, divisor, result);
free(buf);
fclose(fp);
return 0;
}
Если также необходима десятичная часть, просто объявите result как double и добавить к нему результат fmod(number,divisor).
Объяснение того, как это работает
- А
fwriteпишетnumberбайт (в приведенном выше примере это число 123456). rewindсбрасывает указатель файла в начало файла.freadчитает максимумnumber«записи», которыеdivisorпо длине из файла и возвращает количество прочитанных элементов.
Если вы напишете 30 байт, а затем прочитаете файл по 3, вы получите 10 «единиц».30/3 = 10
log(pow(exp(number),0.33333333333333333333)) /* :-) */
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int num = 1234567;
int den = 3;
div_t r = div(num,den); // div() is a standard C function.
printf("%d\n", r.quot);
return 0;
}
Вы можете использовать встроенную сборку (зависит от платформы), например, для x86: (также работает для отрицательных чисел)
#include <stdio.h>
int main() {
int dividend = -42, divisor = 5, quotient, remainder;
__asm__ ( "cdq; idivl %%ebx;"
: "=a" (quotient), "=d" (remainder)
: "a" (dividend), "b" (divisor)
: );
printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
return 0;
}
Использовать итоа для преобразования в строку с основанием 3.Отбрось последнее трит и конвертируем обратно в 10-ю систему.
// Note: itoa is non-standard but actual implementations
// don't seem to handle negative when base != 10.
int div3(int i) {
char str[42];
sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
if (i>0) // Remove sign if positive
str[0] = ' ';
itoa(abs(i), &str[1], 3); // Put ternary absolute value starting at str[1]
str[strlen(&str[1])] = '\0'; // Drop last digit
return strtol(str, NULL, 3); // Read back result
}
(примечание:см. «Редактирование 2» ниже для лучшей версии!)
Это не так сложно, как кажется, потому что вы сказали «без использования [..] + [..] операторы".См. ниже, если вы хотите запретить использование + персонаж все вместе.
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
for (unsigned i = 0; i < by; i++)
cmp++; // that's not the + operator!
floor = r;
r++; // neither is this.
}
return floor;
}
тогда просто скажи div_by(100,3) делить 100 к 3.
Редактировать:Вы можете продолжить и заменить ++ также оператор:
unsigned inc(unsigned x) {
for (unsigned mask = 1; mask; mask <<= 1) {
if (mask & x)
x &= ~mask;
else
return x & mask;
}
return 0; // overflow (note that both x and mask are 0 here)
}
Редактировать 2:Немного более быстрая версия без использования какого-либо оператора, содержащего +,-,*,/,% персонажи.
unsigned add(char const zero[], unsigned const x, unsigned const y) {
// this exploits that &foo[bar] == foo+bar if foo is of type char*
return (int)(uintptr_t)(&((&zero[x])[y]));
}
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
cmp = add(0,cmp,by);
floor = r;
r = add(0,r,1);
}
return floor;
}
Мы используем первый аргумент add функция, поскольку мы не можем обозначить тип указателей без использования * символ, за исключением списков параметров функций, где синтаксис type[] идентичен type* const.
Кстати, вы можете легко реализовать функцию умножения, используя аналогичный трюк для использования 0x55555556 трюк, предложенный АндрейТ:
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
Это легко возможно на Сетунь компьютер.
Чтобы разделить целое число на 3, сдвиг вправо на 1 место.
Однако я не уверен, возможно ли реализовать соответствующий компилятор C на такой платформе.Возможно, нам придется немного расширить правила, например, интерпретировать «минимум 8 бит» как «способное хранить как минимум целые числа от -128 до +127».
Поскольку это от Oracle, как насчет таблицы поиска заранее рассчитанных ответов?:-D
Вот мое решение:
public static int div_by_3(long a) {
a <<= 30;
for(int i = 2; i <= 32 ; i <<= 1) {
a = add(a, a >> i);
}
return (int) (a >> 32);
}
public static long add(long a, long b) {
long carry = (a & b) << 1;
long sum = (a ^ b);
return carry == 0 ? sum : add(carry, sum);
}
Во-первых, обратите внимание, что
1/3 = 1/4 + 1/16 + 1/64 + ...
Теперь все остальное просто!
a/3 = a * 1/3
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
Теперь все, что нам нужно сделать, это сложить эти сдвинутые по битам значения a!Упс!Однако мы не можем складывать, поэтому вместо этого нам придется написать функцию сложения, используя побитовые операторы!Если вы знакомы с побитовыми операторами, мое решение должно выглядеть довольно простым...но на тот случай, если вы этого не сделаете, в конце я приведу пример.
Еще следует отметить, что сначала я сдвигаю влево на 30!Это делается для того, чтобы дроби не округлялись.
11 + 6
1011 + 0110
sum = 1011 ^ 0110 = 1101
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100
Now you recurse!
1101 + 0100
sum = 1101 ^ 0100 = 1001
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000
Again!
1001 + 1000
sum = 1001 ^ 1000 = 0001
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000
One last time!
0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17
carry = (0001 & 10000) << 1 = 0
Done!
Это просто дополнение, которому вы научились в детстве!
111
1011
+0110
-----
10001
Эта реализация неуспешный потому что мы не можем сложить все члены уравнения:
a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i
Предположим, что результат div_by_3(a) = х, тогда x <= floor(f(a, i)) < a / 3.Когда a = 3k, мы получаем неправильный ответ.
Чтобы разделить 32-битное число на 3, его нужно умножить на 0x55555556 а затем возьмите старшие 32 бита 64-битного результата.
Теперь осталось только реализовать умножение с помощью битовых операций и сдвигов...
Еще одно решение.Это должно обрабатывать все целые числа (включая отрицательные целые числа), за исключением минимального значения целого числа, которое необходимо обрабатывать как жестко запрограммированное исключение.По сути, это деление путем вычитания, но только с использованием битовых операторов (сдвиг, xor и дополнение).Для более высокой скорости вычитается 3 * (убывающая степень 2).В C# он выполняет около 444 таких вызовов DivideBy3 за миллисекунду (2,2 секунды для 1 000 000 делений), так что это не ужасно медленно, но и далеко не так быстро, как простой x/3.Для сравнения, хорошее решение Куди примерно в 5 раз быстрее этого.
public static int DivideBy3(int a) {
bool negative = a < 0;
if (negative) a = Negate(a);
int result;
int sub = 3 << 29;
int threes = 1 << 29;
result = 0;
while (threes > 0) {
if (a >= sub) {
a = Add(a, Negate(sub));
result = Add(result, threes);
}
sub >>= 1;
threes >>= 1;
}
if (negative) result = Negate(result);
return result;
}
public static int Negate(int a) {
return Add(~a, 1);
}
public static int Add(int a, int b) {
int x = 0;
x = a ^ b;
while ((a & b) != 0) {
b = (a & b) << 1;
a = x;
x = a ^ b;
}
return x;
}
Это C#, потому что он мне пригодился, но отличия от C должны быть незначительными.
Это действительно очень легко.
if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;
(Я, конечно, для краткости опустил часть программы.) Если программисту надоест все это печатать, я уверен, что он или она могли бы написать отдельную программу, которая сгенерирует это для него.Я случайно знаю одного оператора, /, это значительно упростило бы его работу.
Использование счетчиков является базовым решением:
int DivBy3(int num) {
int result = 0;
int counter = 0;
while (1) {
if (num == counter) //Modulus 0
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 1
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 2
return result;
counter = abs(~counter); //++counter
result = abs(~result); //++result
}
}
Также легко выполнить функцию модуля, проверьте комментарии.
Это классический алгоритм деления по основанию 2:
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t mod3[6] = { 0,1,2,0,1,2 };
uint32_t x = 1234567; // number to divide, and remainder at the end
uint32_t y = 0; // result
int bit = 31; // current bit
printf("X=%u X/3=%u\n",x,x/3); // the '/3' is for testing
while (bit>0)
{
printf("BIT=%d X=%u Y=%u\n",bit,x,y);
// decrement bit
int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
uint32_t r = x>>bit; // current remainder in 0..5
x ^= r<<bit; // remove R bits from X
if (r >= 3) y |= 1<<bit; // new output bit
x |= mod3[r]<<bit; // new remainder inserted in X
}
printf("Y=%u\n",y);
}
Напишите программу на языке Паскаль и используйте DIV оператор.
Поскольку вопрос помечен с, вы, вероятно, можете написать функцию на Паскале и вызывать ее из программы на языке C;метод для этого зависит от системы.
Но вот пример, который работает в моей системе Ubuntu с Free Pascal. fp-compiler пакет установлен.(Я делаю это из чистого неуместного упрямства;Я не утверждаю, что это полезно.)
divide_by_3.pas :
unit Divide_By_3;
interface
function div_by_3(n: integer): integer; cdecl; export;
implementation
function div_by_3(n: integer): integer; cdecl;
begin
div_by_3 := n div 3;
end;
end.
main.c :
#include <stdio.h>
#include <stdlib.h>
extern int div_by_3(int n);
int main(void) {
int n;
fputs("Enter a number: ", stdout);
fflush(stdout);
scanf("%d", &n);
printf("%d / 3 = %d\n", n, div_by_3(n));
return 0;
}
Строить:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
Пример исполнения:
$ ./main
Enter a number: 100
100 / 3 = 33
int div3(int x)
{
int reminder = abs(x);
int result = 0;
while(reminder >= 3)
{
result++;
reminder--;
reminder--;
reminder--;
}
return result;
}
Не проверил, опубликован ли уже этот ответ.Если программу необходимо расширить до плавающих чисел, числа можно умножить на 10 * необходимое число точности, а затем снова применить следующий код.
#include <stdio.h>
int main()
{
int aNumber = 500;
int gResult = 0;
int aLoop = 0;
int i = 0;
for(i = 0; i < aNumber; i++)
{
if(aLoop == 3)
{
gResult++;
aLoop = 0;
}
aLoop++;
}
printf("Reulst of %d / 3 = %d", aNumber, gResult);
return 0;
}
Это должно работать для любого делителя, а не только для трех.В настоящее время только для неподписанных, но расширить его до подписанных не должно быть так уж сложно.
#include <stdio.h>
unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do {
one = ~two & bor;
two ^= bor;
bor = one<<1;
} while (one);
return two;
}
unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;
if (!bot || top < bot) return 0;
for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;
for (result=0; shift--; bot >>= 1 ) {
result <<=1;
if (top >= bot) {
top = sub(top,bot);
result |= 1;
}
}
return result;
}
int main(void)
{
unsigned arg,val;
for (arg=2; arg < 40; arg++) {
val = bitdiv(arg,3);
printf("Arg=%u Val=%u\n", arg, val);
}
return 0;
}
Было бы обманом использовать / оператор «за кадром», используя eval и конкатенация строк?
Например, в Javascript вы можете сделать
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
С использованием до н. э. Математика в PHP:
<?php
$a = 12345;
$b = bcdiv($a, 3);
?>
MySQL (это интервью от Oracle)
> SELECT 12345 DIV 3;
a:= 12345;
b:= a div 3;
язык ассемблера x86-64:
mov r8, 3
xor rdx, rdx
mov rax, 12345
idiv r8
Первое, что я придумал.
irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub(' ', ' ').size }
=> #<Proc:0x0000000205ae90@(irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222
РЕДАКТИРОВАТЬ: Извините, не заметил тег C.Но я думаю, вы можете использовать идею форматирования строк...
Следующий скрипт создает программу на языке C, которая решает проблему без использования операторов * / + - %:
#!/usr/bin/env python3
print('''#include <stdint.h>
#include <stdio.h>
const int32_t div_by_3(const int32_t input)
{
''')
for i in range(-2**31, 2**31):
print(' if(input == %d) return %d;' % (i, i / 3))
print(r'''
return 42; // impossible
}
int main()
{
const int32_t number = 8;
printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')
С использованием Калькулятор чисел Hacker's Delight Magic
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
Где ФМА это стандартная библиотечная функция, определенная в math.h заголовок.
Как насчет этого подхода (С#)?
private int dividedBy3(int n) {
List<Object> a = new Object[n].ToList();
List<Object> b = new List<object>();
while (a.Count > 2) {
a.RemoveRange(0, 3);
b.Add(new Object());
}
return b.Count;
}
Я думаю, что правильный ответ:
Почему бы мне не использовать базовый оператор для выполнения базовой операции?
Решение с использованием библиотечная функция fma(), работает для любого положительного числа:
#include <stdio.h>
#include <math.h>
int main()
{
int number = 8;//Any +ve no.
int temp = 3, result = 0;
while(temp <= number){
temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
result = fma(result, 1, 1);
}
printf("\n\n%d divided by 3 = %d\n", number, result);
}
Использовать кблас, включенный в состав платформы OS X Accelerate.
[02:31:59] [william@relativity ~]$ cat div3.c
#import <stdio.h>
#import <Accelerate/Accelerate.h>
int main() {
float multiplicand = 123456.0;
float multiplier = 0.333333;
printf("%f * %f == ", multiplicand, multiplier);
cblas_sscal(1, multiplier, &multiplicand, 1);
printf("%f\n", multiplicand);
}
[02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031
Первый:
x/3 = (x/4) / (1-1/4)
Затем выясните, как решить x/(1 - y):
x/(1-1/y)
= x * (1+y) / (1-y^2)
= x * (1+y) * (1+y^2) / (1-y^4)
= ...
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))
с у = 1/4:
int div3(int x) {
x <<= 6; // need more precise
x += x>>2; // x = x * (1+(1/2)^2)
x += x>>4; // x = x * (1+(1/2)^4)
x += x>>8; // x = x * (1+(1/2)^8)
x += x>>16; // x = x * (1+(1/2)^16)
return (x+1)>>8; // as (1-(1/2)^32) very near 1,
// we plus 1 instead of div (1-(1/2)^32)
}
Хотя он использует +, но кто-то уже реализует побитовое добавление.
Хорошо, я думаю, мы все согласны с тем, что это не проблема реального мира.Просто ради интереса, вот как это сделать с помощью Ada и многопоточности:
with Ada.Text_IO;
procedure Divide_By_3 is
protected type Divisor_Type is
entry Poke;
entry Finish;
private
entry Release;
entry Stop_Emptying;
Emptying : Boolean := False;
end Divisor_Type;
protected type Collector_Type is
entry Poke;
entry Finish;
private
Emptying : Boolean := False;
end Collector_Type;
task type Input is
end Input;
task type Output is
end Output;
protected body Divisor_Type is
entry Poke when not Emptying and Stop_Emptying'Count = 0 is
begin
requeue Release;
end Poke;
entry Release when Release'Count >= 3 or Emptying is
New_Output : access Output;
begin
if not Emptying then
New_Output := new Output;
Emptying := True;
requeue Stop_Emptying;
end if;
end Release;
entry Stop_Emptying when Release'Count = 0 is
begin
Emptying := False;
end Stop_Emptying;
entry Finish when Poke'Count = 0 and Release'Count < 3 is
begin
Emptying := True;
requeue Stop_Emptying;
end Finish;
end Divisor_Type;
protected body Collector_Type is
entry Poke when Emptying is
begin
null;
end Poke;
entry Finish when True is
begin
Ada.Text_IO.Put_Line (Poke'Count'Img);
Emptying := True;
end Finish;
end Collector_Type;
Collector : Collector_Type;
Divisor : Divisor_Type;
task body Input is
begin
Divisor.Poke;
end Input;
task body Output is
begin
Collector.Poke;
end Output;
Cur_Input : access Input;
-- Input value:
Number : Integer := 18;
begin
for I in 1 .. Number loop
Cur_Input := new Input;
end loop;
Divisor.Finish;
Collector.Finish;
end Divide_By_3;
