C 언어: 비트 연산(bitwise operation)_000021
C언어: x * y
/// 연산
x * y
/// 예제
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | #include <stdio.h> #include <stdlib.h> #include <time.h> void show_binary(int value); // decimal to bianry int sign_switch(int x); // sign switch int adder(int x, int y); // adder int multiplier(int x, int y); // simple multiplier //--------------------- core gate ----------------------------------------------- extern inline int not_gate(int x) { return (~x); } // not gate extern inline int or_gate(int x, int y) { return (x | y); } // or gate extern inline int and_gate(int x, int y) { return (x & y); } // and gate extern inline int xor_gate(int x, int y) { return (x ^ y); } // xor gate extern inline int l_shift(int x, int bits) { return (x << bits); } // left shift extern inline int r_shift(int x, int bits) { return (x >> bits); } // right shift //------------------------------------------------------------------------------- //---------------------- // main() implementation int main(void) { int plus01, plus02, minus01, minus02; int mul = 0; srand(time(NULL)); plus01 = r_shift(rand(), 24); plus02 = r_shift(rand(), 24); mul = multiplier(plus01, plus02); printf(" %4d: ", plus01); /* << */ show_binary(plus01); /* << */ puts(""); printf(" %4d: ", plus02); /* << */ show_binary(plus02); /* << */ puts(""); printf("%4d * %4d = %7d: ", plus01, plus02, mul); /* << */ show_binary(mul); /* << */ puts(""); puts("----------------------------------------------------------"); plus01 = r_shift(rand(), 24); minus01 = sign_switch(r_shift(rand(), 24)); mul = multiplier(plus01, minus01); printf(" %4d: ", plus01); /* << */ show_binary(plus01); /* << */ puts(""); printf(" %4d: ", minus01); /* << */ show_binary(minus01); /* << */ puts(""); printf("%4d * %4d = %7d: ", plus01, minus01, mul); /* << */ show_binary(mul); /* << */ puts(""); puts("----------------------------------------------------------"); minus01 = sign_switch(r_shift(rand(), 24)); plus01 = r_shift(rand(), 24); mul = multiplier(minus01, plus01); printf(" %4d: ", minus01); /* << */ show_binary(minus01); /* << */ puts(""); printf(" %4d: ", plus01); /* << */ show_binary(plus01); /* << */ puts(""); printf("%4d * %4d = %7d: ", minus01, plus01, mul); /* << */ show_binary(mul); /* << */ puts(""); puts("----------------------------------------------------------"); minus01 = sign_switch(r_shift(rand(), 24)); minus02 = sign_switch(r_shift(rand(), 24)); mul = multiplier(minus01, minus02); printf(" %4d: ", minus01); /* << */ show_binary(minus01); /* << */ puts(""); printf(" %4d: ", minus02); /* << */ show_binary(minus02); /* << */ puts(""); printf("%4d * %4d = %7d: ", minus01, minus02, mul); /* << */ show_binary(mul); /* << */ puts(""); return 0; } //------------------------------------- // multiplier() implementation (simple) int multiplier(int x, int y) { int mul = 0; int sign = 0; // make absolute value of integer if (x < 0) { x = sign_switch(x); sign++; } if (y < 0) { y = sign_switch(y); sign++; } // swap x and y, because of while loop(if x > y, it's efficient) // approximation (x = 2^(n-1) < y = 2^(n)) if (x < y) { x = xor_gate(x, y); y = xor_gate(x, y); x = xor_gate(x, y); } // reference: https://www.geeksforgeeks.org/russian-peasant-multiply-two-numbers-using-bitwise-operators/ while (y > 0) { if (and_gate(y, 1)) mul = adder(mul, x); x = l_shift(x, 1); y = r_shift(y, 1); } // sign is 0 or 2 (positive result) // if sign is 1 (negative result) if (and_gate(sign, 1)) mul = sign_switch(mul); return mul; // think different! } //----------------------------- // sign_switch() implementation int sign_switch(int x) { return adder(not_gate(x), 1); } //----------------------- // adder() implementation int adder(int x, int y) { int carry, sum; // reference: https://en.wikipedia.org/wiki/Bitwise_operations_in_C do { carry = and_gate(x, y) << 1; // carry 00001000 00110000 00100100 10000000 (<-left shift) sum = xor_gate(x, y); // x 00001110 11110000 11100110 10000000 x = carry; // + y 00101000 00110100 00110100 11100011 y = sum; //---------------------------------------------------------- } while(carry != 0); return sum; // think different! } //----------------------------- // show_binary() implementation void show_binary(int value) { const int MAX_BIT = 32; const int INT_MIN = -2147483648; enum flag { OFF = -1, ON = 1 } sign_switch = OFF; // 필요개념에 의해 정의 int mask = INT_MIN; // 10000000 00000000 00000000 00000000 for (int i = MAX_BIT; i >= 1; i--) { printf("%d", and_gate(value, mask) ? 1 : 0); mask = r_shift(mask, 1); // 1로 right shift하는 것을 방지 if (sign_switch == OFF && i == MAX_BIT) { // 11000000 00000000 00000000 00000000 mask = xor_gate(mask, INT_MIN); // -> 01000000 00000000 00000000 00000000 sign_switch = ON; } if (and_gate((i-1), 7) == 0) printf(" "); // 가독성을 위한 분리자 } // think different! } | cs |
* 실행환경: Linux(5.7.6-x86_64-linode136)
* 컴파일러: gcc (Ubuntu 6.5.0-2ubuntu1~14.04.1) 6.5.0 20181026
- 당신을 응원합니다. -
댓글
댓글 쓰기