*, /, +,-, % 연산자를 사용하지 않고 숫자를 3으로 나눕니다.
어떻게 사용하지 않고 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
Idiotic 조건은 멍청한 해결책을 요구합니다 :
#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;
}
itoa 를 사용 하여 기본 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
FWIW, AndreyT가0x55555556 제안한 트릭을 사용하는 유사한 트릭을 사용하여 곱셈 함수를 쉽게 구현할 수 있습니다 .
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
정수를 3으로 나누려면 오른쪽으로 1 자리 이동 합니다.
그래도 그런 플랫폼에서 준수 C 컴파일러를 구현하는 것이 엄격하게 가능한지 확실하지 않습니다. "최소 8 비트"를 "최소 -128에서 +127까지의 정수를 보유 할 수있는 능력"으로 해석하는 것처럼 규칙을 약간 늘려야 할 수도 있습니다.
Oracle에서 온 것이므로 미리 계산 된 답변의 조회 테이블은 어떻습니까? :-디
내 해결책은 다음과 같습니다.
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 의 reslut을 가정하고 x <= floor(f(a, i)) < a / 3. 때 a = 3k, 우리는 잘못된 답변을 얻을.
32 비트 숫자를 3으로 나누려면 곱한 0x55555556다음 64 비트 결과의 상위 32 비트를 가져옵니다.
이제 남은 일은 비트 연산과 시프트를 사용하여 곱셈을 구현하는 것입니다.
또 다른 해결책. 이것은 하드 코딩 된 예외로 처리되어야하는 int의 최소값을 제외한 모든 int (음수 정수 포함)를 처리해야합니다. 이것은 기본적으로 빼기로 나누지 만 비트 연산자 (시프트, xor, & 및 보수) 만 사용합니다. 더 빠른 속도를 위해 3 *을 뺍니다 (2의 거듭 제곱 감소). C #에서는 밀리 초당 약 444 개의 DivideBy3 호출 (1,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);
}
파스칼로 프로그램을 작성하고 DIV연산자를 사용하십시오 .
질문에 c 태그가 지정되어 있으므로 Pascal로 함수를 작성하고 C 프로그램에서 호출 할 수 있습니다. 그렇게하는 방법은 시스템에 따라 다릅니다.
그러나 여기에 Free 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(""));
}
<?php
$a = 12345;
$b = bcdiv($a, 3);
?>
MySQL (오라클의 인터뷰)
> 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));
}
''')
사용하여 해커의 기쁨 매직 번호 계산기
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);
}
OS X의 Accelerate 프레임 워크의 일부로 포함 된 cblas를 사용하십시오 .
[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)
}
사용 +하지만 누군가 이미 비트 연산으로 add를 구현합니다.
좋아요 저는 이것이 실제 문제가 아니라는 데 우리 모두 동의한다고 생각합니다. 재미를 위해 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;
참고 URL : https://stackoverflow.com/questions/11694546/divide-a-number-by-3-without-using-operators
'your programing' 카테고리의 다른 글
| 프로그램을 중단하지 않고 전체 트레이스 백을 인쇄하는 방법은 무엇입니까? (0) | 2020.09.30 |
|---|---|
| 명령 줄에서 'git commit -m'에 줄 바꿈 추가 (0) | 2020.09.30 |
| VS2013에서 참조 횟수를 숨기는 방법은 무엇입니까? (0) | 2020.09.30 |
| 어셈블리 파일 버전을 어떻게 얻을 수 있습니까? (0) | 2020.09.30 |
| Scala 대 Groovy 대 Clojure (0) | 2020.09.30 |