*,/,+,-,%연산자를 사용하지 않고 숫자를 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;
}
Jim이 언급했듯이 다음과 같은 이유로 이것이 작동합니다.
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;
}
Base 3 문자열로 변환 할 마지막 TRIT 를 다시 기반 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으로 나누려면 오른쪽으로 바로 이동
나는 그런 플랫폼에서 conforming c 컴파일러를 구현할 수있는 엄격한 여부를 확신하지 못한다.우리는 "적어도 8 비트 이상"으로 -128에서 +127 "으로 유지할 수있는"적어도 8 비트 "로 해석하는 것과 같이 규칙을 조금 늘려야 할 수도 있습니다.
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, 그러면 x <= floor(f(a, i)) < a / 3.언제 a = 3k, 우리는 잘못된 대답을 얻습니다.
32 비트 숫자를 3으로 나눌 수 있습니다. GeneraCodicicetagode가 곱한 다음 64 비트 결과의 상단 32 비트를 가져갈 수 있습니다.
이제는 비트 운영을 사용하여 곱셈을 구현하는 것입니다 ...
또 다른 해결책.이는 int의 최소값을 제외하고 모든 int (nicuve int 포함)를 처리해야하며, 이는 하드 코딩 된 예외로 처리해야합니다.이것은 기본적으로 뺄셈에 의한 부서를 수행하지만 비트 연산자 (Shifts, XOR 및 보완) 만 사용합니다.빠른 속도를 높이면 3 * (2의 감소)을 뺍니다.C #에서는이 DiviDebby3 호출의 444 (1,000,000 개 분할의 경우 2.2 초)이므로 끔찍한 느리지 않고 단순한 x / 3만큼 빨리 가까이있는 곳은 아닙니다.비교할 때, Coodey의 멋진 해결책은 이것보다 약 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);
}
PASCAL에 프로그램을 작성하고 DIV 연산자를 사용하십시오.
질문은 C , 당신파스칼에서 기능을 작성하고 C 프로그램에서 전화를 걸 수 있습니다.그렇게하는 방법은 시스템 특정입니다.
그러나 무료 Pascal fp-compiler 패키지가 설치된 Ubuntu 시스템에서 작동하는 예제는 다음과 같습니다.(나는 깎아 낸 깎아 낸 완고함에서 이것을하고있다. 나는 이것이 유용하다는 것을 주장하지 않는다.)
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;
}
이는 3 개뿐만 아니라 모든 제수에서 작동해야합니다.현재 서명되지만 가입하도록 확장하는 것은 어렵지 않아야합니다.
#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 연산자 "뒤에 뒤의 뒷면"을 사용하는 것이 바람직합니다.
예를 들어 javacript에서
를 수행 할 수 있습니다.function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
BC 수학 http : //en.wikipedia.org/wiki/php "rel="nofollow "> PHP :
<?php
$a = 12345;
$b = bcdiv($a, 3);
?>
"Nofollow"> MySQL (Oracle에서 인터뷰)
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
편집 : 죄송합니다, tag the generacodicicetagcode를 알지 못했습니다.그러나 문자열 형식에 대한 아이디어를 사용할 수 있습니다. 추측 ...
다음 스크립트는 연산자 * / + - %를 사용하지 않고 문제를 해결하는 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));
}
''')
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
여기서 FMA 는 math.h 헤더에 정의 된 표준 라이브러리 함수입니다.
이 접근법 (C #)은 어떻습니까?
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);
}
cblas 포함OS X의 일부가 가속 프레임 워크의 일부로
[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))
y= 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;
