# 2018q3 Homework (bits)
<contributed by < [`siahuat0727`](https://github.com/siahuat0727) >
[作業 E07: bits](https://hackmd.io/s/r14wRqUjQ)
## 在 Ubuntu Linux x86 64-bit 安裝 32-bit 過程
```
$ sudo apt update
$ sudo apt install gcc-multilib libc6-dev:i386 gcc:i386
```
若出現其他 dependencies 就把它們都先安裝好。
```
gcc:i386 : Depends: cpp:i386 (>= 4:7.3.0-3ubuntu2.1) but it is not going to be installed
Depends: gcc-7:i386 (>= 7.3.0-27~) but it is not going to be installed
```
## 測試有些 function 有可能超時
應該是單純的測資過多，開發環境測試的情況是 floatIsEqual、 floatIsLess、 floatPower2 會超時，修改 btest.c 裡面的 TIMEOUT_LIMIT 的值（原本是 10， 我改成 30）後就可以順利通過了。
## 暫時關閉 cppcheck
:::info
:question:
`Shifting signed 32-bit value by 31 bits is undefined behaviour` 看了好久還是覺得跟自己的理解有點出入。
1. 對於 **E1 << 31**，若 **E1** 是 signed type，我們知道所有 **非0 << 31** 都會發生 overflow，按規格書的描述將發生 undefined behavior，但就算嘗試執行 **0 << 31** 也會出現該錯誤訊息，不知道只是單純 cppcheck 不去考慮這點還是哪裡理解錯誤？
2. 如果沒理解錯，像是 **0xFF << 28** 按規格書的說法應該是 undefined behavior，那麼我們在這裡該不該使用它的結果？
3. 而對於 **E1 >> 31** 就更奇怪了，若 **E1** 是 signed type，當 **E1** 是非負時是 **well-defined** 的，只有 **E1** 是負數時才是 **implementation-defined**，但 cppcheck 做 **static** analysis 卻把所有 **E1(signed type) >> 31** 歸爲 undefined behavior？（對於 `>>` 應該只有 shift amount 爲負或大於等於 width of left operand 時才會發生 undefined behavior？）
:::
如果上述理解沒錯，我想若 `E1(int type) << 31` 是 undefined behavior，那麼 `E1 << 30 << 1` 也會是 undefined behavior（因爲還沒大於等於 32，所以是考慮有沒有 overflow）。而對於這份作業來說，限制 `E1 >> 31` 的使用沒意義，`E1 << n` 發生 undefined behavior 的情況又測不出來，所以先 disable cppcheck 。
> **C99 standard N1256**
**6.5.7 Bitwise shift operators**
3 The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
4 The result of **E1 << E2** is **E1** left-shifted **E2** bit positions; vacated bits are filled with zeros. If **E1** has an unsigned type, the value of the result is **E1 × $2^{E2}$** , reduced modulo one more than the maximum value representable in the result type. If **E1** has a signed type and nonnegative value, and **E1 × $2^{E2}$** is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
5 The result of **E1 >> E2** is **E1** right-shifted **E2** bit positions. If **E1** has an unsigned type or if **E1** has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of **E1 / $2^{E2}$**. If **E1** has a signed type and a negative value, the resulting value is implementation-defined.
## 常用技巧集
```cpp
// xxx_mask means the value is 11.......11 if xxx else 00......00
x_is_neg_mask = x >> 31;
x_is_nonneg_mask = ~(x >> 31);
x_is_0_mask = !x << 31 >> 31;
x_is_not_0_mask = !x + ~0;
// lower n bits set to 1 (for 0 <= n <= 31 only)
lower_n_1_mask = (1 << n) + ~0; // or ~(~0 << n)
// lower n bits set to 0 (for 0 <= n <= 31 only)
lower_n_0_mask = ~0 << n;
// upper n bits set to 1 (for 0 <= n <= 31 only)
upper_n_1_mask = 1 << 31 >> n << 1;
// upper n bits set to 0 (for 0 <= n <= 31 only)
upper_n_0_mask = ~(1 << 31 >> n << 1);
// value = 1 if x equals to y else 0
is_x_y_same = !(x ^ y);
```
## 進度
Datalab 的部分已完成！
`Total points: 228/228`
持續優化中...
感覺很多都能在規定的最大 op 數的一半之內完成，若有緣人比較時知道有更快的方法願意分享的話**非常歡迎留言**！
### vim 小技巧
由于小改動的频率非常高（修改變數名、添加註解、發現某些 function 不符合要求、突然想到/發現更少 op 數的方法），所以儘量把註解及過程寫在程式碼裡面，以便每次更新時覆蓋整個文件。
用 vim recording 功能生成以下符合 markdown 格式的各 function：
（若沒新增其他以 /* 作爲任一行開頭的註解）
```
$ cp bits.c gen.md
$ vim gen.md
```
刪掉最前面的作業說明後，任意位置（normal mode 下）輸入：
```mediawiki
qq/^\/\*<cr>j2wyw2kI### <esc>po<cr>```C<esc>nn?}<cr>o```<esc>q
84@q
```
第一行是將操作過程記錄在 key q 中（就 vim 的基本操作，只是用的時候要考慮是否適用於其他 function）
第二行爲重複 84 次（共 85 function）
也可以寫成 map 就不用每次重新输入，以帶有顯示 op 數的版本舉例
在 .vimrc 中添加
```mediawiki
let mapleader = ","
nmap <leader>g /^\/\*<cr>j2wyw2kI### <esc>pmao<cr>```C<esc>/{<cr>k$v2by`aa-> <esc>p/Max ops<cr>$yiw`a2ea/<esc>p/^\/\*<cr>n?}<cr>o```<esc>
```
實際使用時只需要
```mediawiki
qq,gq
84@q
```
### absVal -> 4/10 ops
```C
/*
* absVal - absolute value of x
* Example: absVal(-1) = 1.
* You may assume -TMax <= x <= TMax
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
* Rating: 4
*/
int absVal(int x) // 4 ops
{
int neg_mask = x >> 31;
// Return x if x is nonnegative else ones' complement + 1 (two's complement)
return (x ^ neg_mask) + (neg_mask & 1);
}
```
### addOK -> 6/20 op
```C
/*
* addOK - Determine if can compute x+y without overflow
* Example: addOK(0x80000000, 0x80000000) = 0,
* addOK(0x80000000, 0x70000000) = 1,
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int addOK(int x, int y) // 6 op
{
/*
* Observe:
* Return 0 (overflow) when (+,0) + (+,0) => (-) or (-) + (-) => (+,0),
* that is, sign of x and y are same and sign of x (or y) and sum are
* different. Since we can compute whether two signs are DIFFERENT faster,
* convert the observation to sign of x and sum are DIFFERENT and sign of y
* and sum are DIFFERENT.
*
* See also addOK_7()
*/
int sum = x + y;
return !(((x ^ sum) & (y ^ sum)) >> 31);
}
int addOK_7(int x, int y) // 7 op
{
// See addOK_9(), reduce ops by delaying getting sign
int sum = x + y;
return (((x ^ y) | ~(sum ^ x)) >> 31) & 1;
}
int addOK_9(int x, int y) // 9 ops
{
int sign_x = x >> 31;
int sign_y = y >> 31;
int sign_sum = (x + y) >> 31;
// return 1 if sign of x and y are different or sign of sum and x are same
return ((sign_x ^ sign_y) | ~(sign_sum ^ sign_x)) & 1;
}
```
### allEvenBits -> 7/12 ops
```C
/*
* allEvenBits - return 1 if all even-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allEvenBits(int x) // 7 ops
{
int hex5555 = (0x55 << 8) | 0x55;
int hex55555555 = (hex5555 << 16) | hex5555;
return !((x & hex55555555) ^ hex55555555);
}
int allEvenBits_9(int x) // 9 ops
{
x = x & x >> 16;
x = x & x >> 8;
x = x & x >> 4;
x = x & x >> 2;
return x & 1;
}
```
### allOddBits -> 7/12 ops
```C
/*
* allOddBits - return 1 if all odd-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) // 7 ops
{
int hexAAAA = (0xAA << 8) | 0xAA;
int hexAAAAAAAA = (hexAAAA << 16) | hexAAAA;
return !((x & hexAAAAAAAA) ^ hexAAAAAAAA);
}
int allOddBits_10(int x) // 10 ops
{
x = x & x >> 16;
x = x & x >> 8;
x = x & x >> 4;
x = x & x >> 2;
return (x >> 1) & 1;
}
```
### anyEvenBit -> 7/12 ops
```C
/*
* anyEvenBit - return 1 if any even-numbered bit in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples anyEvenBit(0xA) = 0, anyEvenBit(0xE) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int anyEvenBit(int x) // 7 ops
{
int hex5555 = (0x55 << 8) | 0x55;
int hex55555555 = (hex5555 << 16) | hex5555;
return !!(x & hex55555555);
}
int anyEvenBit_9(int x) // 9 ops
{
x = x | x >> 16;
x = x | x >> 8;
x = x | x >> 4;
x = x | x >> 2;
return x & 1;
}
```
### anyOddBit -> 7/12 ops
```C
/*
* anyOddBit - return 1 if any odd-numbered bit in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples anyOddBit(0x5) = 0, anyOddBit(0x7) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int anyOddBit(int x) // 7 ops
{
int hexAAAA = (0xAA << 8) | 0xAA;
int hexAAAAAAAA = (hexAAAA << 16) | hexAAAA;
return !!(x & hexAAAAAAAA);
}
int anyOddBit_10(int x) // 10 ops
{
x = x | x >> 16;
x = x | x >> 8;
x = x | x >> 4;
x = x | x >> 2;
return (x >> 1) & 1;
}
```
### bang -> 5/12 ops
```C
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) // 5 ops
{
/*
* Consider sign bit of x and two's complement of x:
* x = 0 => both are 0 WE NEED THIS
* x = tmin => both are 1
* otherwise => exactly one 0 and one 1
*/
int x_twos_comp = ~x + 1;
return ((x | x_twos_comp) >> 31) + 1;
}
int bang_12(int x) // 12 ops
{
x = x | x >> 16;
x = x | x >> 8;
x = x | x >> 4;
x = x | x >> 2;
x = x | x >> 1;
return ~x & 1;
}
```
### bitAnd -> 4/8 ops
```C
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) // 4 ops
{
return ~(~x | ~y);
}
```
### bitCount -> 24/40 ops
```C
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) // 24 ops
{
// See bitCount_30()
int hex0F0F = (0x0F << 8) | 0x0F;
int hex0F0F0F0F = (hex0F0F << 16) | hex0F0F;
int hex33333333 = hex0F0F0F0F ^ (hex0F0F0F0F << 2);
int hex55555555 = hex33333333 ^ (hex33333333 << 1);
x = (x & hex55555555) + ((x >> 1) & hex55555555);
x = (x & hex33333333) + ((x >> 2) & hex33333333);
/*
* Idea from
* http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
* Since x is now 4-bit per group and the maximum number of 1 after add up
* two group is 8, which is representable in 4-bit, so we can do mask after
* add.
* Benefits: save 1 op (no need to mask twice)
*/
x = (x + (x >> 4)) & hex0F0F0F0F;
// Same concept with above but save more ops
x = x + (x >> 8);
x = (x + (x >> 16)) & 0xFF;
return x;
}
int bitCount_30(int x) // 30 ops
{
/*
* Idea: https://www.viseator.com/2017/06/18/CS_APP_DataLab/
*
* Counting parallel and in place
*
* 'x' means ignore the column where '+' means add up the column
* x + x + x + x + x
* consider 8-bit x: |0|1|1|1|0|0|0|1|
* shift 1 bit: |0|1|1|1|0|0|0|1|
* add the specific column: | 01| 10| 00| 01|
* number of bit 1 in each group: | 1 | 2 | 0 | 1 |
*
* repeat similar action x + x + x
* the value of x now: |01|10|00|01|
* shift 2 bit: |01|10|00|01|
* add the specific column: | 0011| 0001|
* number of bit 1 in each group: | 3 | 1 |
*
* repeat similar action x + x
* the value of x now: |0011|0001|
* shift 4 bit: |0011|0001|
* add the specific column: | 00000100|
* number of bit 1 in each group: | 4 | <- the total bit 1 in x
*/
int hex0000FFFF = (0xFF << 8) | 0xFF;
int hex00FF00FF = hex0000FFFF ^ (hex0000FFFF << 8);
int hex0F0F0F0F = hex00FF00FF ^ (hex00FF00FF << 4);
int hex33333333 = hex0F0F0F0F ^ (hex0F0F0F0F << 2);
int hex55555555 = hex33333333 ^ (hex33333333 << 1);
x = (x & hex55555555) + ((x >> 1) & hex55555555);
x = (x & hex33333333) + ((x >> 2) & hex33333333);
x = (x & hex0F0F0F0F) + ((x >> 4) & hex0F0F0F0F);
x = (x & hex00FF00FF) + ((x >> 8) & hex00FF00FF);
x = (x & hex0000FFFF) + ((x >> 16) & hex0000FFFF);
return x;
}
```
### bitMask -> 6/16 ops
```C
/*
* bitMask - Generate a mask consisting of all 1's
* lowbit and highbit
* Examples: bitMask(5, 3) = 0x38
* Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
* If lowbit > highbit, then mask should be all 0's
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int bitMask(int highbit, int lowbit) // 6 ops
{
// Idea from < aben20807 >:
// Use '~0 << lowbit' instead of '~((1 << lowbit) + ~0)'
int ones = ~0; // All bits are set to 1 or decimal -1
int high_mask = ones << lowbit;
int low_mask = ((1 << highbit << 1) + ones);
return high_mask & low_mask;
}
```
### bitMatch -> 8/14 ops
```C
/*
* bitMatch - Create mask indicating which bits in x match those in y
* using only ~ and &
* Example: bitMatch(0x7, 0xE) = 0x6
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitMatch(int x, int y) // 8 ops
{
// (x & y) | (~x & ~y) <- Apply De Morgan's law
return ~(~(x & y) & ~(~x & ~y));
}
```
### bitNor -> 3/8 ops
```C
/*
* bitNor - ~(x|y) using only ~ and &
* Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
* Legal ops: ~ &
* Max ops: 8
* Rating: 1
*/
int bitNor(int x, int y) // 3 ops
{
// De Morgan's law
return ~x & ~y;
}
```
### bitOr -> 4/8 ops
```C
/*
* bitOr - x|y using only ~ and &
* Example: bitOr(6, 5) = 7
* Legal ops: ~ &
* Max ops: 8
* Rating: 1
*/
int bitOr(int x, int y) // 4 ops
{
return ~(~x & ~y);
}
```
### bitParity -> 11/20 ops
```C
/*
* bitParity - returns 1 if x contains an odd number of 0's
* Examples: bitParity(5) = 0, bitParity(7) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
int bitParity(int x) // 11 ops
{
x = x ^ (x >> 16);
x = x ^ (x >> 8);
x = x ^ (x >> 4);
x = x ^ (x >> 2);
x = x ^ (x >> 1);
return x & 1;
}
```
### bitReverse -> 34/45 ops
```C
/*
* bitReverse - Reverse bits in a 32-bit word
* Examples: bitReverse(0x80000002) = 0x40000001
* bitReverse(0x89ABCDEF) = 0xF7D3D591
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 45
* Rating: 4
*/
int bitReverse(int x) // 10 + 24 = 34 ops
{
int hex0000FFFF = (0xFF << 8) | 0xFF;
int hex00FF00FF = hex0000FFFF ^ (hex0000FFFF << 8);
int hex0F0F0F0F = hex00FF00FF ^ (hex00FF00FF << 4);
int hex33333333 = hex0F0F0F0F ^ (hex0F0F0F0F << 2);
int hex55555555 = hex33333333 ^ (hex33333333 << 1);
x = x << 16 | ((x >> 16) & hex0000FFFF);
x = (x & hex00FF00FF) << 8 | ((x >> 8) & hex00FF00FF);
x = (x & hex0F0F0F0F) << 4 | ((x >> 4) & hex0F0F0F0F);
x = (x & hex33333333) << 2 | ((x >> 2) & hex33333333);
x = (x & hex55555555) << 1 | ((x >> 1) & hex55555555);
return x;
}
```
### bitXor -> 8/14 ops
```C
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) // 8 ops
{
// (~x & y) | (x & ~y) <- Apply De Morgan's law
return ~(~(~x & y) & ~(x & ~y));
}
```
### byteSwap -> 14/25 ops
```C
/*
* byteSwap - swaps the nth byte and the mth byte
* Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
* byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
* You may assume that 0 <= n <= 3, 0 <= m <= 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 25
* Rating: 2
*/
int byteSwap(int x, int n, int m) // 14 ops
{
int m_dis = m << 3;
int n_dis = n << 3;
int m_mask = (x >> m_dis) & 0xFF;
int n_mask = (x >> n_dis) & 0xFF;
// Clear mth and nth bytes if m != n (when m == n, x is already the answer)
x = x ^ (m_mask << m_dis) ^ (n_mask << n_dis);
// Set mth and nth bytes that after swap
return x | (m_mask << n_dis) | (n_mask << m_dis);
}
```
### conditional -> 7/16 ops
```C
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) // 7 ops
{
int false_mask = (!x << 31) >> 31;
return (~false_mask & y) | (false_mask & z);
}
```
### countLeadingZero -> 25/50 ops
```C
/*
* countLeadingZero - count the number of zero bits preceding the
* most significant one bit
* Example: countLeadingZero(0x00000F00) = 20,
* countLeadingZero(0x00000001) = 31
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 50
* Rating: 4
*/
int countLeadingZero(int x) // 25 ops
{
/*
* Speed up from countLeadingZero_36()
* Idea: ilog2() https://www.viseator.com/2017/06/18/CS_APP_DataLab/,
* No need to use leading_n_zero as a mask!
*/
int num_zero = 0;
// value = 1 if the leading 16 bits are all zero else 0
int leading_n_zero = !(x >> 16);
int n = leading_n_zero << 4; // n = 16 if leading_n_zero is true
num_zero = n;
x = x << n;
// value = 1 if the leading 8 bits are all zero else 0
leading_n_zero = !(x >> 24);
n = leading_n_zero << 3;
num_zero = num_zero + n;
x = x << n;
// value = 1 if the leading 4 bits are all zero else 0
leading_n_zero = !(x >> 28);
n = leading_n_zero << 2;
num_zero = num_zero + n;
x = x << n;
// value = 1 if the leading 2 bits are all zero else 0
leading_n_zero = !(x >> 30);
n = leading_n_zero << 1;
num_zero = num_zero + n;
x = x << n;
int bit_31_is_zero = !(x >> 31);
num_zero = num_zero + bit_31_is_zero;
int bit_31_to_30_is_zero = !(x >> 30);
num_zero = num_zero + bit_31_to_30_is_zero;
return num_zero;
}
int countLeadingZero_36(int x) // 36 ops
{
// See countLeadingZero_43()
int num_zero = 0;
// value = 11......11 if the leading 16 bits are all zero else 00......00
int leading_n_zero = !(x >> 16) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 16);
x = x << (leading_n_zero & 16);
// value = 11......11 if the leading 8 bits are all zero else 00......00
leading_n_zero = !(x >> 24) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 8);
x = x << (leading_n_zero & 8);
// value = 11......11 if the leading 4 bits are all zero else 00......00
leading_n_zero = !(x >> 28) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 4);
x = x << (leading_n_zero & 4);
/*
* Method above takes 8 ops per iteration,
* but the next interation (8 ops) can only get 2-bit information,
* and we can get 1-bit information in 3 ops.
* Hence, consider the remaining 4 bits seperately will be faster.
*/
int bit_31_is_zero = !(x >> 31);
num_zero = num_zero + bit_31_is_zero;
int bit_31_to_30_is_zero = !(x >> 30);
num_zero = num_zero + bit_31_to_30_is_zero;
int bit_31_to_29_is_zero = !(x >> 29);
num_zero = num_zero + bit_31_to_29_is_zero;
int bit_31_to_28_is_zero = !(x >> 28);
num_zero = num_zero + bit_31_to_28_is_zero;
return num_zero;
}
int countLeadingZero_43(int x) // 43 ops
{
/*
* https://hackmd.io/s/Bk-uxCYxz
* int clz(uint32_t x) {
* if (x == 0) return 32;
* int n = 1;
* if ((x >> 16) == 0) { n += 16; x <<= 16; }
* if ((x >> 24) == 0) { n += 8; x <<= 8; }
* if ((x >> 28) == 0) { n += 4; x <<= 4; }
* if ((x >> 30) == 0) { n += 2; x <<= 2; }
* n = n - (x >> 31);
* return n;
* }
*/
int num_zero = 0;
// value = 11......11 if the leading 16 bits are all zero else 00......00
int leading_n_zero = !(x >> 16) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 16);
x = x << (leading_n_zero & 16);
// value = 11......11 if the leading 8 bits are all zero else 00......00
leading_n_zero = !(x >> 24) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 8);
x = x << (leading_n_zero & 8);
// value = 11......11 if the leading 4 bits are all zero else 00......00
leading_n_zero = !(x >> 28) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 4);
x = x << (leading_n_zero & 4);
// value = 11......11 if the leading 2 bits are all zero else 00......00
leading_n_zero = !(x >> 30) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 2);
x = x << (leading_n_zero & 2);
// value = 11......11 if the leading 1 bits are all zero else 00......00
leading_n_zero = !(x >> 31) << 31 >> 31;
num_zero = num_zero + (leading_n_zero & 1);
x = x << (leading_n_zero & 1);
num_zero = num_zero + !(x >> 31);
return num_zero;
}
```
### copyLSB -> 2/5 ops
```C
/*
* copyLSB - set all bits of result to least significant bit of x
* Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int copyLSB(int x) // 2 ops
{
return (x << 31) >> 31;
}
```
### distinctNegation -> 3/5 ops
```C
/*
* distinctNegation - returns 1 if x != -x.
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 5
* Rating: 2
*/
int distinctNegation(int x) // 3 ops
{
// Goal: Return 1 if x is not 0 (00......00) or tmin (10......00) else 0
int throw_sign_bit = x << 1; // Since !(x << 1) will get warning
return !!throw_sign_bit;
}
int distinctNegation_5(int x) // 5 ops
{
int x_twos_comp = ~x + 1;
// Check if x is different with two's complement of x
return !!(x ^ x_twos_comp);
}
int distinctNegation_5_bang(int x) // 5 ops
{
// Goal: Return 1 if x is not 0 (00......00) or tmin (10......00) else 0
// See bang() (case 1 and 2)
return ((x ^ (~x + 1)) >> 31) & 1;
}
```
### dividePower2 -> 7/15 ops
```C
/*
* dividePower2 - Compute x/(2^n), for 0 <= n <= 30
* Round toward zero
* Examples: dividePower2(15, 1) = 7, dividePower2(-33, 4) = -2
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int dividePower2(int x, int n) // 7 ops
{
/*
* x >> n is equal to floor(x/(2^n)), whether x is nonnegative or negative.
*
* But we want ceil(x/(2^n)) when x is negative, that is, round toward zero.
* And ceil(x/(2^n)) equals to floor((x+(2^n)-1)/(2^n)) when divisor is
* integer. As a result, we add (2^n)-1 to x when x is negative.
*
* See also trueThreeFourths() for the details when x is negative
*/
int neg_mask = x >> 31;
return (x + (neg_mask & ((1 << n) + ~0))) >> n;
}
```
### evenBits -> 4/8 ops
```C
/*
* evenBits - return word with all even-numbered bits set to 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 1
*/
int evenBits(void) // 4 ops
{
int hex55 = 0x55;
int hex5555 = hex55 | (hex55 << 8);
return hex5555 | (hex5555 << 16);
}
```
### ezThreeFourths -> 6/12 ops
```C
/*
* ezThreeFourths - multiplies by 3/4 rounding toward 0,
* Should exactly duplicate effect of C expression (x*3/4),
* including overflow behavior.
* Examples: ezThreeFourths(11) = 8
* ezThreeFourths(-9) = -6
* ezThreeFourths(1073741824) = -268435456 (overflow)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 3
*/
int ezThreeFourths(int x) // 6 ops
{
// See dividePower2()
int x_mul_3 = x + (x << 1);
int x_mul_3_is_neg = x_mul_3 >> 31;
return (x_mul_3 + (x_mul_3_is_neg & 3)) >> 2;
}
// ERROR: Test ezThreeFourths_wrong(-2147483647[0x80000001]) failed...
// Gives -536870912[0xe0000000]. Should be -536870911[0xe0000001]
int ezThreeFourths_wrong(int x)
{
return (x + (x << 1)) >> 2; // Error: Division of negative number
}
```
### fitsBits -> 6/15 ops
```C
/*
* fitsBits - return 1 if x can be represented as an n-bit, two's complement
* integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) // 6 ops
{
int m = 33 + ~n; // => 32 + (~n + 1) => 32 - n
int x_as_n_bit = (x << m) >> m;
return !(x ^ x_as_n_bit); // x == x_as_n_bit
}
```
### fitsShort -> 4/8 ops
```C
/*
* fitsShort - return 1 if x can be represented as a 16-bit, two's complement
* integer.
* Examples: fitsShort(33000) = 0, fitsShort(-32768) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 1
*/
int fitsShort(int x) // 4 ops
{
int x_as_16_bit = (x << 16) >> 16;
return !(x ^ x_as_16_bit);
}
```
### floatAbsVal -> ?/10 ops
```C
/*
* floatAbsVal - Return bit-level equivalent of absolute value of f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's,
* but they are to be interpreted as the bit-level
* representations of single-precision floating point values.
* When argument is NaN, return argument..
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned floatAbsVal(unsigned uf) // 3? ops
{
unsigned uf_abs = uf & 0x7FFFFFFF;
return uf_abs > 0x7F800000 ? uf : uf_abs;
}
```
### floatFloat2Int -> ?/30 ops
```C
/*
* floatFloat2Int - Return bit-level equivalent of expression (int) f
* for floating point argument f.
* Argument is passed as unsigned int, but it is to be
* interpreted as the bit-level representation of a
* single-precision floating point value.
* Anything out of range (including NaN and infinity) should
* return 0x80000000u.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
int floatFloat2Int(unsigned uf) // 21? ops
{
int is_neg = uf >> 31;
int exponent = (uf >> 23) & 0xFF;
int fraction = uf & 0x7FFFFF;
int bias = 127;
int len_fraction = 23;
// (NaN or INF) || greater than values that a 32-bit int can represent
if (exponent == 0xFF || exponent > bias + 31)
return 0x80000000;
// Can be represented as 32-bit int
if (exponent >= bias) {
int power2 = exponent - bias;
if (power2 <= len_fraction)
fraction = fraction >> (len_fraction - power2);
else
fraction = fraction << (power2 - len_fraction);
int value = (1 << power2) | fraction;
return is_neg ? -value : value;
}
// Smaller than values that a 32-bit int can represent
return 0;
}
```
### floatInt2Float -> ?/30 ops
```C
/*
* floatInt2Float - Return bit-level equivalent of expression (float) x
* Result is returned as unsigned int, but it is to be
* interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatInt2Float(int x) // 35? ops
{
// See floatFloat2Int()
if (x == 0)
return 0;
int x_sign = x & 0x80000000;
int x_abs = x_sign ? -x : x; // How about Tmin?
int exponent, fraction;
int bias = 127;
int len_fraction = 23;
int power2 = 31;
while (!(x_abs >> power2) && power2 > 0) {
power2--;
}
exponent = power2 + bias;
fraction = ((1 << power2) - 1) & x_abs;
if (power2 <= len_fraction) {
fraction = fraction << (len_fraction - power2);
} else {
int num_fall_off = power2 - len_fraction;
/*
* Consider round off
* GRS action: https://stackoverflow.com/questions/8981913
*/
int G = x_abs & (1 << num_fall_off);
int R = x_abs & (1 << (num_fall_off - 1));
/*
* Shift twice to avoid undefined bahavior (<< 32), since:
* 24 <= power2 <= 31
* 1 <= num_fall_off <= 8
* We want 'x_abs << (33 - num_fall_off)'
*/
int S = x_abs << (32 - num_fall_off) << 1;
fraction = fraction >> (power2 - len_fraction);
// Check if need to round up or round-to-even
fraction += R && (S || G);
}
return (x_sign | (exponent << len_fraction)) + fraction;
}
```
### floatIsEqual -> ?/25 ops
```C
/*
* floatIsEqual - Compute f == g for floating point arguments f and g.
* Both the arguments are passed as unsigned int's, but
* they are to be interpreted as the bit-level representations
* of single-precision floating point values.
* If either argument is NaN, return 0.
* +0 and -0 are considered equal.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 25
* Rating: 2
*/
int floatIsEqual(unsigned uf, unsigned ug) // 11? ops
{
// return (uf is not NaN && ug is not NaN && (uf equals to ug || both are
// zero))
return (uf & 0x7FFFFFFF) <= 0x7F800000 && (ug & 0x7FFFFFFF) <= 0x7F800000 &&
(uf == ug || !((uf | ug) << 1));
}
```
### floatIsLess -> ?/30 ops
```C
/*
* floatIsLess - Compute f < g for floating point arguments f and g.
* Both the arguments are passed as unsigned int's, but
* they are to be interpreted as the bit-level representations
* of single-precision floating point values.
* If either argument is NaN, return 0.
* +0 and -0 are considered equal.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 3
*/
int floatIsLess(unsigned uf, unsigned ug) // 23? ops
{
// Check if uf is NaN or ug is NaN or both are zero
if ((uf & 0x7FFFFFFF) > 0x7F800000 || (ug & 0x7FFFFFFF) > 0x7F800000 ||
!((uf | ug) << 1))
return 0;
int uf_sign = uf >> 31;
int ug_sign = ug >> 31;
// (uf is neg and ug is pos || (both are neg && uf < ug) ||
// (both are pos && uf > ug))
if (uf_sign > ug_sign ||
(ug_sign == uf_sign && ((ug_sign && ug < uf) || (!ug_sign && uf < ug))))
return 1;
return 0;
}
```
### floatNegate -> ?/10 ops
```C
/*
* floatNegate - Return bit-level equivalent of expression -f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's,
* but they are to be interpreted as the bit-level
* representations of single-precision floating point values.
* When argument is NaN, return argument.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned floatNegate(unsigned uf) // 5? ops
{
int is_NaN = (uf & 0x7FFFFFFF) > 0x7F800000;
// Toggle sign bit if uf is not NaN
return is_NaN ? uf : uf ^ 0x80000000;
}
```
### floatPower2 -> ?/30 ops
```C
/*
* floatPower2 - Return bit-level equivalent of the expression 2.0^x
* (2.0 raised to the power x) for any 32-bit integer x.
*
* The unsigned value that is returned should have the
* identical bit representation as the single-precision
* floating-point number 2.0^x.
* If the result is too small to be represented as a denorm,
* return 0. If too large, return +INF.
*
* Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatPower2(int x) // 12? ops
{
/*
* Observe:
* exp = 2^8, frac = 0 => 2 ^ INF
* exp = 2^8-1, frac = 0 => 2 ^ (128)
* exp = 2, frac = 0 => 2 ^ (-125)
* exp = 1, frac = 0 => 2 ^ (-126)
* exp = 0, frac = 2^23 => 2 ^ (-127)
* exp = 0, frac = 2^22 => 2 ^ (-128)
* exp = 0, frac = 2^0 => 2 ^ (-150)
*/
if (x < -150)
return 0;
if (x <= -127)
return 1 << (x + 127);
if (x <= 128)
return (x + 127) << 23;
return 0x7F800000; // INF;
}
```
### floatScale1d2 -> ?/30 ops
```C
/*
* floatScale1d2 - Return bit-level equivalent of expression 0.5*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's,
* but they are to be interpreted as the bit-level
* representation of single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatScale1d2(unsigned uf) // 12? ops
{
int sign = uf & 0x80000000;
int exponent = uf & 0x7F800000;
if (exponent <= 0x800000) {
// Round-to-even
uf = uf + ((uf & 0x3) == 0x3);
int uf_abs = uf ^ sign;
uf = sign | (uf_abs >> 1);
} else if (exponent < 0x7F800000) {
uf = uf - 0x800000;
}
return uf;
}
```
### floatScale2 -> ?/30 ops
```C
/*
* floatScale2 - Return bit-level equivalent of expression 2*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's,
* but they are to be interpreted as the bit-level representation
* of single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatScale2(unsigned uf) // 8? ops
{
int sign = uf & 0x80000000;
int exponent = uf & 0x7F800000;
int exponent_is_zero = !exponent;
if (exponent_is_zero) {
uf = sign | (uf << 1);
} else if (exponent != 0x7F800000) {
uf = uf + 0x800000;
}
return uf;
}
```
### floatScale64 -> ?/35 ops
```C
/*
* floatScale64 - Return bit-level equivalent of expression 64*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's,
* but they are to be interpreted as the bit-level
* representation of single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 35
* Rating: 4
*/
unsigned floatScale64(unsigned uf) // 15? ops
{
int sign = uf & 0x80000000;
int num_loop = 6;
while (num_loop--) {
int exponent = uf & 0x7F800000;
int exponent_is_zero = !exponent;
if (exponent_is_zero) {
uf = sign | (uf << 1);
} else if (exponent != 0x7F800000) {
uf = uf + 0x800000;
exponent = uf & 0x7F800000;
// Check if grater than INF
if (exponent == 0x7F800000) {
uf = uf & 0xFF800000; // clear fraction
}
}
}
return uf;
}
```
### floatUnsigned2Float -> ?/30 ops
```C
/*
* floatUnsigned2Float - Return bit-level equivalent of expression (float) u
* Result is returned as unsigned int, but it is to be
* interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatUnsigned2Float(unsigned u) // 26? ops
{
if (u) {
int len_fraction = 23;
int greatest_bit_pos = 31;
while (!((1 << greatest_bit_pos) & u)) {
greatest_bit_pos--;
}
int diff = len_fraction - greatest_bit_pos;
int bias = 127;
int exponent = bias + len_fraction - diff; // 127 (bias) + 23 - diff
if (diff >= 0) {
u <<= diff;
} else {
diff = -diff;
// GRS action: https://stackoverflow.com/questions/8981913
int G = u & (1 << diff);
int R = u & (1 << (diff - 1));
int S = u << (33 - diff);
u >>= diff;
// ( Obvious || Round-to-even )
u += R && (S || G);
}
// | sign=0 | exponent | fraction |
u = (exponent << len_fraction) | (u & 0x7FFFFF);
}
return u;
}
```
### getByte -> 3/6 ops
```C
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (least significant) to 3 (most significant)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) // 3 ops
{
return (x >> (n << 3)) & 0xFF;
}
```
### greatestBitPos -> 30/70 ops
```C
/*
* greatestBitPos - return a mask that marks the position of the
* most significant 1 bit. If x == 0, return 0
* Example: greatestBitPos(96) = 0x40
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 70
* Rating: 4
*/
int greatestBitPos(int x) // 30 ops
{
// See countLeadingZero()
int t = x;
int num_zero = 0;
int leading_n_zero = !(t >> 16);
int n = leading_n_zero << 4;
num_zero = n;
t = t << n;
leading_n_zero = !(t >> 24);
n = leading_n_zero << 3;
num_zero = num_zero + n;
t = t << n;
leading_n_zero = !(t >> 28);
n = leading_n_zero << 2;
num_zero = num_zero + n;
t = t << n;
leading_n_zero = !(t >> 30);
n = leading_n_zero << 1;
num_zero = num_zero + n;
t = t << n;
num_zero = num_zero + !(t >> 31) + !(t >> 30);
// if (x != 0) return 1 << (31 - n) else return 0
return !!x << (32 + ~num_zero);
}
int greatestBitPos_61(int x) // 61 ops
{
// bitReverse() -> leastBitPos() -> bitReverse()
int hex0000FFFF = (0xFF << 8) | 0xFF;
int hex00FF00FF = hex0000FFFF ^ (hex0000FFFF << 8);
int hex0F0F0F0F = hex00FF00FF ^ (hex00FF00FF << 4);
int hex33333333 = hex0F0F0F0F ^ (hex0F0F0F0F << 2);
int hex55555555 = hex33333333 ^ (hex33333333 << 1);
int reverse = x << 16 | ((x >> 16) & hex0000FFFF);
reverse = (reverse & hex00FF00FF) << 8 | ((reverse >> 8) & hex00FF00FF);
reverse = (reverse & hex0F0F0F0F) << 4 | ((reverse >> 4) & hex0F0F0F0F);
reverse = (reverse & hex33333333) << 2 | ((reverse >> 2) & hex33333333);
reverse = (reverse & hex55555555) << 1 | ((reverse >> 1) & hex55555555);
// x & (x - 1) clear the least bit
// x ^ (x & (x - 1)) get the least bit
int rev_no_least = reverse ^ (reverse & (reverse + ~0));
x = rev_no_least << 16 | ((rev_no_least >> 16) & hex0000FFFF);
x = (x & hex00FF00FF) << 8 | ((x >> 8) & hex00FF00FF);
x = (x & hex0F0F0F0F) << 4 | ((x >> 4) & hex0F0F0F0F);
x = (x & hex33333333) << 2 | ((x >> 2) & hex33333333);
x = (x & hex55555555) << 1 | ((x >> 1) & hex55555555);
return x;
}
```
### howManyBits -> 34/90 ops
```C
/*
* howManyBits - return the minimum number of bits required to represent x in
* two's complement
* Examples: howManyBits(12) = 5
* howManyBits(298) = 10
* howManyBits(-5) = 4
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int howManyBits(int x) // 34 ops
{
/*
* Trivial method:
* Goal: Return 32 - (max(leading zeros, leading ones) - 1)
*
* return 33 - maximumOfTwo(countLeadingZero(x), countLeadingZero(~x));
* Done! But this method needs 25 + 26 + 13 + 2 = 66 ops
*
* We can use the same concept of counting leading zero to implement this
* function. See countLeadingZero()
*/
int num_bits_redundant = 0;
// value = 11......11 if the leading 17 bits are the same else 00......00
int x_as_16_bit = x << 16 >> 16;
int leading_n_same = !(x_as_16_bit ^ x);
int n = leading_n_same << 4;
num_bits_redundant = num_bits_redundant + n;
x = x << n;
// value = 11......11 if the leading 9 bits are the same else 00......00
leading_n_same = !((x << 8 >> 8) ^ x);
n = leading_n_same << 3;
num_bits_redundant = num_bits_redundant + n;
x = x << n;
// value = 11......11 if the leading 5 bits are the same else 00......00
leading_n_same = !((x << 4 >> 4) ^ x);
n = leading_n_same << 2;
num_bits_redundant = num_bits_redundant + n;
x = x << n;
// value = 11......11 if the leading 3 bits are the same else 00......00
leading_n_same = !((x << 2 >> 2) ^ x);
n = leading_n_same << 1;
num_bits_redundant = num_bits_redundant + n;
x = x << n;
// value = 11......11 if the leading 2 bits are the same else 00......00
leading_n_same = !((x << 1 >> 1) ^ x);
num_bits_redundant = num_bits_redundant + leading_n_same;
// Return 32 - num_bits_redundant
return 33 + ~num_bits_redundant;
}
```
### implication -> 2/5 ops
```C
/*
* implication - return x -> y in propositional logic - 0 for false,
* 1 for true
* Example: implication(1, 1) = 1
* implication(1, 0) = 0
* Legal ops: ! ~ ^ |
* Max ops: 5
* Rating: 2
*/
int implication(int x, int y) // 2 ops
{
return (!x) | y;
}
```
### intLog2 -> 24/90 ops
```C
/*
* intLog2 - return floor(log base 2 of x), where x > 0
* Example: intLog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int intLog2(int x) // 24 ops
{
// See countLeadingZero()
int num_zero = 0;
int leading_n_zero = !(x >> 16);
int n = leading_n_zero << 4; // n = 16 if leading_n_zero is true
num_zero = n;
x = x << n;
leading_n_zero = !(x >> 24);
n = leading_n_zero << 3;
num_zero = num_zero + n;
x = x << n;
leading_n_zero = !(x >> 28);
n = leading_n_zero << 2;
num_zero = num_zero + n;
x = x << n;
leading_n_zero = !(x >> 30);
n = leading_n_zero << 1;
num_zero = num_zero + n;
x = x << n;
// Since x > 0, no need to check if bit 31 and bit 30 are both 0
num_zero = num_zero + !(x >> 31);
// Return 31 - num_zero
return 32 + ~num_zero;
}
```
### isAsciiDigit -> 8/15 ops
```C
/*
* isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters
* '0' to '9')
* Example: isAsciiDigit(0x35) = 1.
* isAsciiDigit(0x3a) = 0.
* isAsciiDigit(0x05) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 3
*/
int isAsciiDigit(int x) // 8 ops
{
// x - 0x30 >= 0 && x - 0x39 <= 0
// x - 0x30 >= 0 && x - 0x3A < 0 , easier to check if a number is negative
// (!((x - 0x30) >> 31)) & ((x - 0x3A) >> 31);
return (!((x + ~0x2F) >> 31)) & ((x + ~0x39) >> 31);
}
```
### isEqual -> 2/5 ops
```C
/*
* isEqual - return 1 if x == y, and 0 otherwise
* Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int isEqual(int x, int y) // 2 ops
{
return !(x ^ y);
}
```
### isGreater -> 10/24 ops
```C
/*
* isGreater - if x > y then return 1, else return 0
* Example: isGreater(4,5) = 0, isGreater(5,4) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isGreater(int x, int y) // 10 ops
{
// Speed up from isGreater_12()
return (((y & ~x) | ~((x ^ y) | (x + ~y))) >> 31) & 1;
}
int isGreater_12(int x, int y) // 12 ops
{
// (x is +,0 && y is -) || (x, y have same sign && (x - y) > 0) <- De Morgan
return ((y >> 31) & !(x >> 31)) | !(((x ^ y) >> 31) | ((x + ~y) >> 31));
}
```
### isLess -> 10/24 ops
```C
/*
* isLess - if x < y then return 1, else return 0
* Example: isLess(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLess(int x, int y) // 10 ops
{
// See isGreater()
// Return isGreater(y, x)
return (((x & ~y) | ~((x ^ y) | (y + ~x))) >> 31) & 1;
}
```
### isLessOrEqual -> 9/24 ops
```C
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) // 9 ops
{
// See isGreater() + De Morgan's law
// Return !isGreater(x, y)
return (((~y | x) & ((x ^ y) | (x + ~y))) >> 31) & 1;
}
int isLessOrEqual_11(int x, int y) // 11 ops
{
// See isLessOrEqual_13()
return (((x & ~y) | ~((x ^ y) | (y + ~x + 1))) >> 31) & 1;
}
int isLessOrEqual_13(int x, int y) // 13 ops
{
// (x is - && y is +,0) || (x, y have same sign && (y - x) >= 0)
return ((x >> 31) & !(y >> 31)) | !(((x ^ y) >> 31) | ((y + ~x + 1) >> 31));
}
```
### isNegative -> 2/6 ops
```C
/*
* isNegative - return 1 if x < 0, return 0 otherwise
* Example: isNegative(-1) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int isNegative(int x) // 2 ops
{
return (x >> 31) & 1;
}
```
### isNonNegative -> 2/6 ops
```C
/*
* isNonNegative - return 1 if x >= 0, return 0 otherwise
* Example: isNonNegative(-1) = 0. isNonNegative(0) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int isNonNegative(int x) // 2 ops
{
return !(x >> 31);
}
```
### isNonZero -> 5/10 ops
```C
/*
* isNonZero - Check whether x is nonzero using
* the legal operators except !
* Examples: isNonZero(3) = 1, isNonZero(0) = 0
* Legal ops: ~ & ^ | + << >>
* Max ops: 10
* Rating: 4
*/
int isNonZero(int x) // 5 ops
{
// Sign bit of both zero and two's complement of zero is 0, see Bang()
return ((x | (~x + 1)) >> 31) & 1;
}
```
### isNotEqual -> 3/6 ops
```C
/*
* isNotEqual - return 0 if x == y, and 1 otherwise
* Examples: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int isNotEqual(int x, int y) // 3 ops
{
return !!(x ^ y);
}
```
### isPallindrome -> 36/45 ops
```C
/*
* isPallindrome - Return 1 if bit pattern in x is equal to its mirror image
* Example: isPallindrome(0x01234567E6AC2480) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 45
* Rating: 4
*/
int isPallindrome(int x) // faster? 36 ops
{
// See bitReverse()
int hex0000FFFF = (0xFF << 8) | 0xFF;
int hex00FF00FF = hex0000FFFF ^ (hex0000FFFF << 8);
int hex0F0F0F0F = hex00FF00FF ^ (hex00FF00FF << 4);
int hex33333333 = hex0F0F0F0F ^ (hex0F0F0F0F << 2);
int hex55555555 = hex33333333 ^ (hex33333333 << 1);
int reverse = x << 16 | ((x >> 16) & hex0000FFFF);
reverse = (reverse & hex00FF00FF) << 8 | ((reverse >> 8) & hex00FF00FF);
reverse = (reverse & hex0F0F0F0F) << 4 | ((reverse >> 4) & hex0F0F0F0F);
reverse = (reverse & hex33333333) << 2 | ((reverse >> 2) & hex33333333);
reverse = (reverse & hex55555555) << 1 | ((reverse >> 1) & hex55555555);
return !(x ^ reverse);
}
```
### isPositive -> 4/8 ops
```C
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 2
*/
int isPositive(int x) // 4 ops
{
return !(x >> 31 | !x); // isPositive_5() + De Morgan's law
}
int isPositive_5(int x) // 5 ops
{
return (!(x >> 31)) & (!!x); // nonnegative and not zero
}
```
### isPower2 -> 8/20 ops
```C
/*
* isPower2 - returns 1 if x is a power of 2, and 0 otherwise
* Examples: isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
* Note that no negative number is a power of 2.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
int isPower2(int x) // 8 ops
{
// (x & (x-1)) == 0 && x > 0
// !(x & (x + ~0)) & !(x >> 31) & !!x 11 ops
// Apply De Morgan's law
return !((x & (x + ~0)) | (x >> 31) | !x);
}
```
### isTmax -> 7/10 ops
```C
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmax(int x) // 7 ops
{
// See isTmax_8() + De Morgan's law
int x_plus_1 = x + 1;
return !(~(x ^ x_plus_1) | !~x);
}
int isTmax_8(int x) // 8 ops
{
// Observe: ~(x ^ (x+1)) only equal to 0 when x is tmax or -1
int x_plus_1 = x + 1;
// ~(x ^ (x+1)) equal to 0 && x is not -1
return !~(x ^ x_plus_1) & !!~x;
}
int isTmax_shift(int x) // Can't use shift
{
int tmax = (0 << 31);
return !(x ^ tmax);
}
```
### isTmin -> 7/10 ops
```C
/*
* isTmin - returns 1 if x is the minimum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmin(int x) // 7 ops
{
// See isTmax()
int x_minus_1 = x + ~0;
return !(~(x ^ x_minus_1) | !x);
}
int isTmin_shift(int x) // Can't use shift
{
int tmin = 1 << 31;
return !(x ^ tmin);
}
```
### isZero -> 1/2 ops
```C
/*
* isZero - returns 1 if x == 0, and 0 otherwise
* Examples: isZero(5) = 0, isZero(0) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 2
* Rating: 1
*/
int isZero(int x) // 1 ops
{
return !x;
}
```
### leastBitPos -> 4/6 ops
```C
/*
* leastBitPos - return a mask that marks the position of the
* least significant 1 bit. If x == 0, return 0
* Example: leastBitPos(96) = 0x20
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int leastBitPos(int x) // 4 ops
{
int x_no_least_bit = x & (x + ~0);
return x ^ x_no_least_bit;
}
```
### leftBitCount -> 26/50 ops
```C
/*
* leftBitCount - returns count of number of consective 1's in
* left-hand (most significant) end of word.
* Examples: leftBitCount(-1) = 32, leftBitCount(0xFFF0F0F0) = 12
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 50
* Rating: 4
*/
int leftBitCount(int x) // 26 ops
{
// Convert to counting leading zeros, see countLeadingZero()
x = ~x;
int num_zero = 0;
int leading_n_zero = !(x >> 16);
int n = leading_n_zero << 4;
num_zero = n;
x = x << n;
leading_n_zero = !(x >> 24);
n = leading_n_zero << 3;
num_zero = num_zero + n;
x = x << n;
leading_n_zero = !(x >> 28);
n = leading_n_zero << 2;
num_zero = num_zero + n;
x = x << n;
leading_n_zero = !(x >> 30);
n = leading_n_zero << 1;
num_zero = num_zero + n;
x = x << n;
num_zero = num_zero + !(x >> 31) + !(x >> 30);
return num_zero;
}
```
### logicalNeg -> 6/12 ops
```C
/*
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int logicalNeg(int x) // 6 ops
{
// See bang()
int x_twos_comp = ~x + 1;
return (((x | x_twos_comp) >> 31) ^ 1) & 1;
}
```
### logicalShift -> 6/20 ops
```C
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) // 6 ops
{
int mask = ~(1 << 31 >> n << 1);
return (x >> n) & mask;
}
int logicalShift_9(int x, int n) // 9 ops
{
int sign = (x >> 31) & 1;
// Clear sign bit to 0 and set it after shift
// return ((x ^ (sign << 31)) >> n) | (sign << (31 - n));
return ((x ^ (sign << 31)) >> n) | (sign << (32 + ~n));
}
```
### maximumOfTwo -> 13/20 ops
```C
/*
* maximumOfTwo - compute the maximum of two integers without branching
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
int maximumOfTwo(int x, int y) // 13 ops
{
// See isGreater() and conditional()
int x_is_greater_mask = ((y & ~x) | ~((x ^ y) | (x + ~y))) >> 31;
return (x_is_greater_mask & x) | (~x_is_greater_mask & y);
}
```
### minimumOfTwo -> 13/20 ops
```C
/*
* minimumOfTwo - compute the minimum of two integers without branching
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
int minimumOfTwo(int x, int y) // 13 ops
{
// see isLess() and conditional()
int x_is_less_mask = ((x & ~y) | ~((x ^ y) | (y + ~x))) >> 31;
return (x_is_less_mask & x) | (~x_is_less_mask & y);
}
```
### minusOne -> 1/2 ops
```C
/*
* minusOne - return a value of -1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 2
* Rating: 1
*/
int minusOne(void) // 1 ops
{
return ~0;
}
```
### multFiveEighths -> 6/12 ops
```C
/*
* multFiveEighths - multiplies by 5/8 rounding toward 0.
* Should exactly duplicate effect of C expression (x*5/8),
* including overflow behavior.
* Examples: multFiveEighths(77) = 48
* multFiveEighths(-22) = -13
* multFiveEighths(1073741824) = 13421728 (overflow)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 3
*/
int multFiveEighths(int x) // 6 ops
{
int x_mul_5 = x + (x << 2);
return (x_mul_5 + ((x_mul_5 >> 31) & 7)) >> 3;
}
```
### negate -> 2/5 ops
```C
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) // 2 ops
{
return ~x + 1;
}
```
### oddBits -> 4/8 ops
```C
/*
* oddBits - return word with all odd-numbered bits set to 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 2
*/
int oddBits(void) // 4 ops
{
int hexAAAA = 0xAA | (0xAA << 8);
return hexAAAA | (hexAAAA << 16);
}
```
### remainderPower2 -> 10/20 ops
```C
/*
* remainderPower2 - Compute x%(2^n), for 0 <= n <= 30
* Negative arguments should yield negative remainders
* Examples: remainderPower2(15, 2) = 3, remainderPower2(-35, 3) = -3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int remainderPower2(int x, int n) // 10 ops
{
/*
* Observe:
* For nonnegative x, return x & (2^n - 1)
* For negative x and remainder is not 0,
* return x & (2^n - 1) with upper 32 - n bits set to 1
*/
int ones = ~0; // All bits are set to 1 or decimal -1
int remainder_mask = (1 << n) + ones;
int remainder = x & remainder_mask;
int sign_mask = x >> 31 << n;
int remainder_is_not_0_mask = !remainder + ones;
return (sign_mask & remainder_is_not_0_mask) | remainder;
}
int remainderPower2_16(int x, int n) // faster, 16 ops
{
int x_sign = x >> 31;
int x_abs = (x ^ x_sign) + (x_sign & 1);
int remainder_mask = (1 << n) + ~0;
int remainder_abs = x_abs & remainder_mask;
int remainder_sign = (x & (!!remainder_abs << 31)) >> 31;
// Return remainder_abs two's complement if remainder should be negative
return (remainder_abs ^ remainder_sign) + (remainder_sign & 1);
}
```
### replaceByte-> 6/10 ops
```C
/*
* replaceByte(x,n,c) - Replace byte n in x with c
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: replaceByte(0x12345678, 1, 0xab) = 0x1234ab78
* You can assume 0 <= n <= 3 and 0 <= c <= 255
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
* Rating: 3
*/
int replaceByte(int x, int n, int c) // 6 ops
{
int n_dis = n << 3;
int clear_mask = 0xFF << n_dis;
int new_mask = c << n_dis;
return (x & ~clear_mask) | new_mask;
}
```
### rotateLeft -> 9/25 ops
```C
/*
* rotateLeft - Rotate x to the left by n
* Can assume that 0 <= n <= 31
* Examples: rotateLeft(0x87654321, 4) = 0x76543218
* Legal ops: ~ & ^ | + << >> !
* Max ops: 25
* Rating: 3
*/
int rotateLeft(int x, int n) // 9 ops
{
int keep_mask = (1 << n) + ~0; // (1 << n) - 1
int fall_off = (x >> (33 + ~n)) & keep_mask; // 33 + ~n => 32 - n
return (x << n) | fall_off;
}
```
### rotateRight -> 12/25 ops
```C
/*
* rotateRight - Rotate x to the right by n
* Can assume that 0 <= n <= 31
* Examples: rotateRight(0x87654321, 4) = 0x76543218
* Legal ops: ~ & ^ | + << >> !
* Max ops: 25
* Rating: 3
*/
int rotateRight(int x, int n) // change neg to pos maybe faster? 12 ops
{
int keep_mask = (1 << n) + ~0;
int shift_dis = 33 + ~n; // 32 - n
int fall_off = (x & keep_mask) << shift_dis;
int clear_mask = keep_mask << shift_dis;
return ((x >> n) & ~clear_mask) | fall_off;
}
```
### satAdd -> 13/30 ops
```C
/*
* satAdd - adds two numbers but when positive overflow occurs, returns
* maximum possible value, and when negative overflow occurs,
* it returns minimum positive value.
* Examples: satAdd(0x40000000, 0x40000000) = 0x7fffffff
* satAdd(0x80000000, 0xffffffff) = 0x80000000
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 30
* Rating: 4
*/
int satAdd(int x, int y) // 13 ops
{
int sum = x + y;
int no_overflow_mask = ((x ^ y) | ~(sum ^ x)) >> 31;
int tmin = 1 << 31;
int sum_is_neg = sum >> 31;
// return (no_overflow_mask & sum) |
// (~no_overflow_mask & (sum < 0 ? tmax : tmin));
return (no_overflow_mask & sum) | (~no_overflow_mask & (tmin ^ sum_is_neg));
}
```
### satMul2 -> 10/20 ops
```C
/*
* satMul2 - multiplies by 2, saturating to Tmin or Tmax if overflow
* Examples: satMul2(0x30000000) = 0x60000000
* satMul2(0x40000000) = 0x7FFFFFFF (saturate to TMax)
* satMul2(0x80000001) = 0x80000000 (saturate to TMin)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int satMul2(int x) // 10 ops
{
int x_mul_2 = x << 1;
int overflow_mask = (x_mul_2 ^ x) >> 31;
int tmin = 1 << 31;
int x_mul_2_is_neg = x_mul_2 >> 31;
return (~overflow_mask & x_mul_2) |
(overflow_mask & (tmin ^ (x_mul_2_is_neg)));
}
```
### satMul3 -> 14/25 ops
```C
/*
* satMul3 - multiplies by 3, saturating to Tmin or Tmax if overflow
* Examples: satMul3(0x10000000) = 0x30000000
* satMul3(0x30000000) = 0x7FFFFFFF (Saturate to TMax)
* satMul3(0x70000000) = 0x7FFFFFFF (Saturate to TMax)
* satMul3(0xD0000000) = 0x80000000 (Saturate to TMin)
* satMul3(0xA0000000) = 0x80000000 (Saturate to TMin)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 25
* Rating: 3
*/
int satMul3(int x) // 14 ops
{
int x_mul_2 = x << 1;
int x_mul_3 = x_mul_2 + x;
int overflow_mask = ((x_mul_2 ^ x) | (x_mul_3 ^ x)) >> 31;
int tmax = ~(1 << 31);
int x_is_neg = x >> 31;
return (~overflow_mask & x_mul_3) | (overflow_mask & (tmax ^ (x_is_neg)));
}
```
### sign -> 3/10 ops
```C
/*
* sign - return 1 if positive, 0 if zero, and -1 if negative
* Examples: sign(130) = 1
* sign(-23) = -1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
* Rating: 2
*/
int sign(int x) // 3 ops
{
return (x >> 31) | !!x;
}
```
### signMag2TwosComp -> 6/15 ops
```C
/*
* signMag2TwosComp - Convert from sign-magnitude to two's complement
* where the MSB is the sign bit
* Example: signMag2TwosComp(0x80000005) = -5.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 4
*/
int signMag2TwosComp(int x) // 6 ops
{
// See twosComp2SignMag()
int neg_mask = x >> 31;
int x_sign = neg_mask << 31;
int x_without_sign = x ^ x_sign;
int x_twos_comp_if_neg = (x_without_sign ^ neg_mask) + (neg_mask & 1);
return x_twos_comp_if_neg;
}
int signMag2TwosComp_15(int x) // faster, 15 ops
{
int no_sign_bit = x << 1; // Since !(x << 1) has warning
x = x & ~(!(no_sign_bit) << 31); // Convert -0 to +0
int neg_mask = x >> 31;
int x_abs = x & ~(1 << 31);
return (neg_mask & (~x_abs + 1)) | (~neg_mask & x);
}
```
### specialBits -> 2/3 ops
```C
/*
* specialBits - return bit pattern 0xffca3fff
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 3
* Rating: 1
*/
int specialBits(void) // 2 ops
{
return ~(0xD7 << 14);
}
```
### subtractionOK -> 8/20 ops
```C
/*
* subtractionOK - Determine if can compute x-y without overflow
* Example: subtractionOK(0x80000000, 0x80000000) = 1,
* subtractionOK(0x80000000, 0x70000000) = 0,
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int subtractionOK(int x, int y) // 8 ops
{
/*
* Observe:
* Return 0 (overflow) when (+,0) - (-) => (-) or (-) - (+,0) => (+,0),
* that is, sign of x and y are different and sign of x and result are
* different.
*
* See addOK()
*/
int diff = x + ~y + 1;
return !(((x ^ y) & (x ^ diff)) >> 31);
}
int subtractionOK_13(int x, int y) // 13 ops
{
/*
* Reuse addOK(x, -y). However, since -Tmin equals to Tmin in c,
* the result of subtraction(x, Tmin) and addOK(x, -Tmin)
* should be the opposite.
*
* For example, if addOK(x, Tmin) returns ok, then addOK(x, -Tmin) is
* equals to addOK(x, Tmin) and will return ok with the result
* x + Tmin, but the value we want to represent is x - Tmin.
*/
int y_neg = ~y + 1;
int sum = x + y_neg;
// See addOK()
int x_add_y_neg_is_OK = (((x ^ y_neg) | ~(sum ^ x)) >> 31) & 1;
int tmin = 1 << 31;
int y_is_Tmin = !(y ^ tmin);
// Toggle the result if y is Tmin
return x_add_y_neg_is_OK ^ y_is_Tmin;
}
```
### thirdBits -> 4/8 ops
```C
/*
* thirdBits - return word with every third bit (starting from the LSB)
* set to 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 1
*/
int thirdBits(void) // 4 ops
{
// 0x49249249
int hex9249 = (0x92 << 8) | 0x49;
return (hex9249 << 15) | hex9249;
}
int thirdBits_6(void) // 6 ops
{
return (0x49 << 24) | (0x24 << 16) | (0x92 << 8) | 0x49;
}
```
### tmax -> 2/4 ops
```C
/*
* tmax - return maximum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmax(void) // 2 ops
{
return ~(1 << 31);
}
```
### tmin -> 1/4 ops
```C
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) // 1 ops
{
return 1 << 31;
}
```
### trueFiveEighths -> 11/25 op
```C
/*
* trueFiveEighths - multiplies by 5/8 rounding toward 0,
* avoiding errors due to overflow
* Examples: trueFiveEighths(11) = 6
* trueFiveEighths(-9) = -5
* trueFiveEighths(0x30000000) = 0x1E000000 (no overflow)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 25
* Rating: 4
*/
int trueFiveEighths(int x) // 11 op
{
// See trueThreeFourths() for the concept
int x_div_8 = x >> 3;
int remainder = x & 0x7; // The remainder of x/8
int x_div_8_mul_5 = (x_div_8 << 2) + x_div_8;
int x_is_neg = x >> 31;
int remainder_mul_5 = (remainder << 2) + remainder;
int carry = (remainder_mul_5 + (x_is_neg & 0x7)) >> 3;
return x_div_8_mul_5 + carry;
}
```
### trueThreeFourths -> 11/20 op
```C
/*
* trueThreeFourths - multiplies by 3/4 rounding toward 0,
* avoiding errors due to overflow
* Examples: trueThreeFourths(11) = 8
* trueThreeFourths(-9) = -6
* trueThreeFourths(1073741824) = 805306368 (no overflow)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
int trueThreeFourths(int x) // 11 op
{
/*
* Since we have to avoid errors due to overflow, we can calculate
* the result of x/4 with remainder first and then calculate the
* result of 3*(x/4) + 3*remainder.
*
* For negative x, since the right shift perform division that rounds
* towards negative infinity, we must add one to it if there is any
* remainder after division so that the result is rounding towards 0.
*/
int x_div_4 = x >> 2;
int remainder = x & 0x3; // The remainder of x/4
int x_div_4_mul_3 = (x_div_4 << 1) + x_div_4;
int x_is_neg = x >> 31;
int remainder_mul_3 = (remainder << 1) + remainder;
int carry = (remainder_mul_3 + (x_is_neg & 0x3)) >> 2;
return x_div_4_mul_3 + carry;
}
```
### twosComp2SignMag -> 6/15 ops
```C
/*
* twosComp2SignMag - Convert from two's complement to sign-magnitude
* where the MSB is the sign bit
* You can assume that x > TMin
* Example: twosComp2SignMag(-5) = 0x80000005.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 4
*/
int twosComp2SignMag(int x) // 6 ops
{
// See absVal()
int neg_mask = x >> 31;
int x_sign = neg_mask << 31;
int x_abs = (x ^ neg_mask) + (neg_mask & 1);
return x_sign | x_abs;
}
```
### upperBits -> 7/10 ops
```C
/*
* upperBits - pads n upper bits with 1's
* You may assume 0 <= n <= 32
* Example: upperBits(4) = 0xF0000000
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
* Rating: 1
*/
int upperBits(int n) // 7 ops
{
/*
* If directly return ~0 << (32 - n), the result is only correct when
* 1 <= n <= 32.
* However, if n is 0, the return value should be 0 and we will compute
* ~0 << (32 - 0), that is, ~0 << 32 which behavior is undefined.
* Therefore, we can mask the shift amount with 0x0 if n is 0 to avoid
* this undefined behavior.
*/
// value = 11......11 if n != 0 else 00......00
int n_is_not_0_mask = !n + ~0;
return n_is_not_0_mask << ((33 + ~n) & n_is_not_0_mask);
}
int upperBits_undefined_behavior(int n) // 6 ops
{
/* INTEGER CODING RULES:
* You may assume that your machine:
* 3. Has unpredictable behavior when shifting if the shift amount
* is less than 0 or greater than 31.
*/
// >> -1 is has unpredictable behavior! (when n == 0)
return (!!n << 31) >> (n + ~0);
}
int upperBits_9(int n) // 9 ops
{
// return n ? (1 << 31) >> (n-1) : 0;
int n_is_0 = (!n << 31) >> 31;
return ~n_is_0 & ((1 << 31) >> (n + ~0));
}
```
## 開發環境
```
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping: 9
CPU MHz: 826.723
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5616.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-7
```
Sign in with Wallet
Connect another wallet