Recently, we bumped into an odd behavior on a shift operation. A code we were debugging was doing a left shift on an integer (1) for 125 times. We were expecting the result to be 0 but oddly the result was 536870912. After consulting our friend Google, we got this explanation:
C99 standard, section 6.5.7 "Bitwise shift operators",
page 84:
"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."
Apparently, the operation was undefined and the behavior is implementation specific. We tried running the code in C and Java; and found out that if the operator is greater than the operand, in this case the size of the operand is 32, the operand is shifted by "operator modulo size-of-operand" times (1 % (125 mod 32)).
I guess we learn new things everyday! ^_^
Monday, March 15, 2010
Thursday, January 14, 2010
Code a division operation by a specific value without a division operator?
Even though the semester is already done, I've decided to continue this blog because its a great way to keep track of what I've learned and practice my writing. Also, because I didn't start the year right, this is my way of getting myself back on track!
Anyway, the subject of this post was asked to me and my colleagues by one of our seniors. He told us that back then there weren't much and they encountered this odd problem while on a project. At first, subtracting the dividend by the divisor while counting the number of times it has been subtracted seemed like a good idea but this solution is very slow. We got the right solution thanks to my colleague IC.
Objective: Divide any given number by a specific number without using the divider operation.
Conditions:
1. The process of multiplication, addition and bit shifting are available.
2. The memory registers are larger than the size of the integer to be divided.
3. Floating point numbers are not supported.
Sample Case: Divide any given 16-bit integer by 48 using a 32-bit register.
Solution:
Let x be the given number, d be the divisor and c be the constant multiplier which is divisible by two.
Hint: x/d is just equal to (x*c)/(d*c )
1. Determine a constant value of 1/48 which will be used as part of the multiplier. Note that a number divided by 48 is equal to that same number multiplied by 1/48:
1/48 = 0.020833333333333333333333333333333
2. Choose a multiplier that will not cause an overflow by dividing the size of the register to the maximum integer value. We are just looking for a specific multiplier that when multiplied by 0xFFFF (the maximum value for a 16 bit integer), will not be greater than 0xFFFFFFFF (the 32-bit register):
(0xFFFF * 1/48)c <= 0xFFFFFFFF so,
c = 0xFFFFFFFF / (0xFFFF * 1/48) = 0x300030 = 0b1100000000000000110000
3. Reduce this number into the highest number divisible by two because we can only use shift operations:
0b1100000000000000110000 can be reduced to 0b1000000000000000000000 which can easily be obtained since this is just 1 << 21.
4. Multiply the inverse constant of the divider by the number above:
0.20833333333333333333333333333333 * 0b1000000000000000000000 = 43690
5. To prevent any round down errors, round up the constant multiplier by adding one:
43690 + 1 = 43691
6. Multiply this constant to the given integer number and divide it with the same multiplier from step 3.
The final equation would then be the following:
(x * 43691) >> 21
Which is accurate until 1 << 15
I'm not a Math wizard so corrections, comments and suggestions are very much welcomed! ^_^
Anyway, the subject of this post was asked to me and my colleagues by one of our seniors. He told us that back then there weren't much and they encountered this odd problem while on a project. At first, subtracting the dividend by the divisor while counting the number of times it has been subtracted seemed like a good idea but this solution is very slow. We got the right solution thanks to my colleague IC.
Objective: Divide any given number by a specific number without using the divider operation.
Conditions:
1. The process of multiplication, addition and bit shifting are available.
2. The memory registers are larger than the size of the integer to be divided.
3. Floating point numbers are not supported.
Sample Case: Divide any given 16-bit integer by 48 using a 32-bit register.
Solution:
Let x be the given number, d be the divisor and c be the constant multiplier which is divisible by two.
Hint: x/d is just equal to (x*c)/(d*c )
1. Determine a constant value of 1/48 which will be used as part of the multiplier. Note that a number divided by 48 is equal to that same number multiplied by 1/48:
1/48 = 0.020833333333333333333333333333333
2. Choose a multiplier that will not cause an overflow by dividing the size of the register to the maximum integer value. We are just looking for a specific multiplier that when multiplied by 0xFFFF (the maximum value for a 16 bit integer), will not be greater than 0xFFFFFFFF (the 32-bit register):
(0xFFFF * 1/48)c <= 0xFFFFFFFF so,
c = 0xFFFFFFFF / (0xFFFF * 1/48) = 0x300030 = 0b1100000000000000110000
3. Reduce this number into the highest number divisible by two because we can only use shift operations:
0b1100000000000000110000 can be reduced to 0b1000000000000000000000 which can easily be obtained since this is just 1 << 21.
4. Multiply the inverse constant of the divider by the number above:
0.20833333333333333333333333333333 * 0b1000000000000000000000 = 43690
5. To prevent any round down errors, round up the constant multiplier by adding one:
43690 + 1 = 43691
6. Multiply this constant to the given integer number and divide it with the same multiplier from step 3.
The final equation would then be the following:
(x * 43691) >> 21
Which is accurate until 1 << 15
I'm not a Math wizard so corrections, comments and suggestions are very much welcomed! ^_^
Subscribe to:
Posts (Atom)