-
Notifications
You must be signed in to change notification settings - Fork 6
CS 33 (Fall '16)
Contributed by Sahil Gandhi.
You are given two numbers that are passed into a function. Find the sum of these two numbers WITHOUT using operators like ++, +, --, -, *, /, and of that type. The ONLY valid options are &, |, <<, >>, and !. You may use loops or recursion, whichever you are more comfortable with.
If you see in the solution, the carry bit is obtained by anding the two values together while the sum is by xoring them. This can easily be seen when adding two one bit numbers (let's take 1 and 1). 1 & 1 = 1 so there is a carry of 1, and 1 ^ 1 = 0 which means the sum is 0. If we keep repeating this for each of the bits found in b, then we can add the sum of the two values together quite fast without using any other kinds of operators.
int addingWithoutRegOperators(int a, int b) {
if (b == 0)
return a;
else if (a == 0)
return b;
while (b) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}Contributed by Yaacov Tarko.
Your problem description. Remember to wrap in-line code in ticks!
The following program assumes the following declarations:
int x = rand();
int y = rand();
int ux = (unsigned) x;
int uy = (unsigned) y;
Will each of the following statements ALWAYS evaluate to true? If so, explain. If not, give an example.
#1
(x^y)^x == ((x+y)^y)^(x+y) ;
#2
(x+y)>0 == (x>0) || (y>0);
#3
( (ux<<28)>>28) == ux ) == (ux & ~15 == 0 ) || (ux & ~15 == ~15 );
#4
( ((ux << 28) >> 28) == ((x << 28 ) >> 28 ) || ( (x > 15) || (x < -15) );
#1 always evaluates to true. Both sides of the expression are equivalent to y. #2 evaluates to false when signed overflow occurs. For example, if x and y are both large positive numbers, x+y can be negative. #3 always evaluates to true, since unsigned integer shifts use logical shifts. The (ux & !15 == ~15) term is a diversion; in reality the result of the term on the left side of the equality operator will always be the same as the result of (ux & ~15 == 0 ). #4 evaluates to false when the fourth smallest significant bit of x is a one and x is between 15 and -15. In that case, ux << 28 >> 28 fills the most significant 28 bits with zeroes and x << 28 >> 28 fills the most significant 28 bits with ones.
Kyle Liang.
What is the difference between CISC and RISC?
CISC - More operations, less general purpose registers, Shorter program length, Slower clock speed, Variable length instructions, x86-64, Data and memory can be accessed in the same instruction,
RISC - Less operations, more general purpose registers, Longer program length, Faster clock speed, Fixed length instructions, MIPS, Data and memory instructions are separated,
And the most important difference between CISC and RISC is that their first characters differ.
Contributed by Vincent Cheng.
Before you lies an ancient treasure chest, and the only obstacle that stands in your way is a single password. But you have a hint, and next to the chest rests a document hinting at the secret behind the password in GAS (GNU Assembler) syntax. In order to open the chest, the function checkInput(int password) must receive the correct input; failure to do so will obliterate the chest.
checkInput(int):
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl %edi, -4(%rbp)
cmpl $74, -4(%rbp)
jle .L4
cmpl $84, -4(%rbp)
jne .L5
.L4:
call BOOM()
.L5:
movl -4(%rbp), %eax
addl %eax, %eax
movl %eax, -4(%rbp)
cmpl $40, -4(%rbp)
jne .L6
addl $550, -4(%rbp)
.L6:
cmpl $610, -4(%rbp)
jne .L7
subl $600, -4(%rbp)
nop
cmpl $4, -4(%rbp)
jle .L13
jmp .L15
.L7:
cmpl $225, -4(%rbp)
jne .L16
addl $179, -4(%rbp)
jmp .L11
.L15:
addl $2, -4(%rbp)
nop
sarl $2, -4(%rbp)
nop
.L13:
cmpl $3, -4(%rbp)
jne .L11
call openChest()
movl $1, %eax
jmp .L14
.L16:
nop
.L11:
call BOOM()
movl $0, %eax
.L14:
leave
ret
First, looking at some of the starting lines of the code, some limitations on our input becomes clear.
movl %edi, -4(%rbp)
cmpl $74, -4(%rbp)
jle .L4
cmpl $84, -4(%rbp)
jne .L5
Because the first parameter resides in %edi, it is also located at -4(%rbp). According to the labels, if the input is also less than or equal to 74 or equal to 84, the function BOOM() is called.
.L5:
movl -4(%rbp), %eax
addl %eax, %eax
movl %eax, -4(%rbp)
cmpl $40, -4(%rbp)
jne .L6
addl $550, -4(%rbp)
Moving on, we take a look at the segment of code denoted by L5. First, the input is doubled, and then it is compared to 40. If it is not equal to 40, we jump to L6. Note that because of the limitations on the input, double the input can never be 40. So we always jump to L6 for a correct input.
In L6, if our value is not equal to 610, we jump to L7. In L7, no matter what our value is equivalent to, we jump to either L16 or L11. In other words, we always hit the BOOM() function. So it becomes clear that double our password must be 610. In order to reach openChest(), our password must be 305.
As a sanity check, we will check what happens after we do not jump to L7 for an input of 305. 600 is subtracted from our value, leaving 10. Because 10 is not less than 4, we jump to L15, where 2 is added to our value, leaving 12. 12 is shifted right by two bits, leaving 3. And because 3 is equivalent to 3, openChest() is called.
Contributed by Jiaming Zheng.
Assume the following declarations:
int x = rand();
float f = fool(); //f is not NaN
unsigned ux = rand();
For the following C expressions, answer if the statement is always true or not. Note that "=>" represents an implication. A => B means that if you assume A to be true, you should answer the question "is B always true?"
a. (x>>20)==(~(x>>20)+1) => x==(int)(float)x
b. x>ux => (~x+1)<0
c. ux-2>=-2 => ux<=1
a. Yes
b. No
c. Yes
Contributed by Luke Moore.
Write a function named bitCount() that returns the number of 1-bits in the binary representation of its unsigned integer argument.
#include <stdio.h>
#include <string.h>
int bitCount (unsigned int n);
int main (int argc, char *argv[]) {
if (argc == 2)
{
int input = atoi(argv[1]);
printf("%d\n", bitCount(input));
return 0;
}
else if (argc > 2)
{
printf("too many arguments!\n");
}
else
{
printf ("# 1-bits in base 2 representation of %u = %d, should be 0\n",
0, bitCount (0));
printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
1, bitCount (1));
printf ("# 1-bits in base 2 representation of %u = %d, should be 16\n",
2863311530u, bitCount (2863311530u));
printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
536870912, bitCount (536870912));
printf ("# 1-bits in base 2 representation of %u = %d, should be 32\n",
4294967295u, bitCount (4294967295u));
}
return 0;
}
int bitCount (unsigned int n) {
// Your code goes here
}
int bitCount (unsigned int n) {
int counter = 0;
if (n == 0)
return counter;
while (n != 0)
{
if (n & 1 == 1)
{
counter++;
}
n = n >> 1;
}
return counter;
}
Contributed by Shannon Tom.
Consider the following structure:
struct s {
char c[3];
double v;
int x;
int* i[2];
} array[10];
How many bytes would array consume in memory on a IA32 and x86-64 machine?
In IA32, array would consume 320 bytes.
If we let array start at address a+0 bytes, the array of characters would take 3 bytes. The double v would be stored at a+8 because it each primitive data type must be aligned to an address that is a multiple of the number of bytes it requires. The int x would be stored at a+16 to a+20. In IA32, a pointer is 4 bytes long. This means that the array of pointers will start at a+20 and end at a+28. Finally, the overall structure s must be aligned to end at a+32 because each overall structure in an array must be aligned to match the largest alignment of its data types. Overall array would consume 32 * 10 = 320 bytes.
In x86-64, array would consume 400 bytes.
The main difference between switching from IA32 to x86-64 in this problem is that pointers are 8 bytes long instead of 4 bytes long. Up to the integer x, everything should be the same. Since pointers are 8 bytes long, they must be aligned to start at a+24 and end at a+40. There is no need for further alignment of the entire data structure because 40 is a multiple of 8, the largest alignment of the data types. Overall array would consume 40 * 10 = 400 bytes.
Contributed by James Mullen.
Describe how the computer adds two floating point numbers. Describe how the computer multiplies two floating point numbers.
Addition: Given (-1)^S1 M1 2^E1 + (-1)^S2 M2 2^E2 = (-1)^S M 2^E, assume E1 > E2. Align M1 and M2 based on binary, then add them together. S and M result from the addition. Since E1 > E2, E = E1 initially. If M >= 2, right shift M and increment E. If M < 1, left shift M by k until 1 <= M < 2, then decrement E by k. Overflow if E is out of range and round M to fix fraction precision.
Multiplication: Given (-1)^S1 M1 2^E1 * (-1)^S2 M2 2^E2 = (-1)^S M 2^E. S = S1 ^ S2, M = M1*M2, and E = E1 + E2. If M >= 2, right shift M and increment E. If E is out of range, overflow to infinity. Round M to fit fraction precision.
Contributed by Yuhuang Chen.
Say an integer 0x12345678 is saved in the memory. Write down how the Bytes are arranged in the memory for a 32-bit big-endian machine and for a 32-bit little-endian machine.
Memory location: 0 +1 +2 +3 Byte Arrangement for 32-bit big-endian machine: 0x12 0x34 0x56 0x78 Byte Arrangement for 32-bit little-endian machine: 0x78 0x56 0x34 0x12
Remember the endianess affects the arrangement of bytes, not bits. You might be asked to write down the Byte arrangment for a kind of mixed-endian machine, and it might look like: 0x56 0x78 0x12 0x34
Jun Kai Ong.
Suppose we have the following C++ code.
unsigned int u = 25;
int a = 50;
std::cout << u - a << std::endl;
(a) What is the output?
(b) Suppose we check the integer type for a, would it show up as an int or an unsigned int ? Explain your answer.
(a) 2^32 - 25 (4294967271) Why not 2^32 - 26 ? -1 overflows to 2^32 -1. Hence, we can derive a general formula for an arbitrary unsigned integer, a which is -a = 2^32 - a.
(b) int. The type of the variable stored in memory does not change when the expression is evaluated, it is merely converted to an intermediate unsigned integer during the operation to match the unsigned integer on the left.
Contributed by Eric Kong.
You're interning at the Eggert Institute's fledgling Bioinformatics Lab. Now, hard times have fallen on the country, and the government has had to slash funding to the research sector, so, long story short, you're the only CS intern that EIBL can afford. You learn that, besides beer pong, the biologists spend their endless days in the lab analysing genomes--sequences of base pairs consisting of nucleobases denoted by A, C, G, and T.
Despite having dropped out of CS 31, some biologists have managed to write C code to do their dirty work. In their code, genomes are represented as C-strings, as for example "CAAAGAGAATCCTCTTTGAT". As you may know, in practice, genomes are huge! The human genome, for example, contains over three billion base pairs. This is, of course, a problem.
Because you are the only CS intern in the room, the biologists flock to you like flies to a lightbulb, hounding you for ways to compress the data. Having taken CS 33, you do have an idea that might work; it involves storing information at the bit level.
You decide on an encoding scheme: the bit sequence 00 corresponds to the nucleobase A, 01 to C, 10 to G, and 11 to T. In your system, the sequence TAGATCCAGTCCACTC is represented by the bit sequence 11001000110101001011010100011101. This is 32 bits long, and can be packed into an unsigned 32-bit integer.
Part A.
Implement the compression function compressDNA, which takes the first 16 chars starting at the location pointed to by a, and converts it into an unsigned 32-bit integer as above. Note that the datatype uint32_t is equivalent to unsigned int on most modern machines. You may assume that the sequence of chars at a is at least 16 chars long and that all chars are either 'A', 'C', 'G', and 'T'. Furthermore, you may assume that all relevant libraries have been #included.
We graciously provide you the following function prototype:
uint32_t compressDNA(char *a);
Part B.
Implement the extraction function extractDNA, which takes an unsigned 32-bit integer holding nucleobases in compressed format as above, and returns the sequence it represents as a C-string. You may assume that all relevant libraries have been #included. Friendly reminder: void* malloc (size_t size); allocates a memory block of size size.
We selflessly provide you the following function prototype:
char* extractDNA(uint32_t u);
Part C.
What is the compression ratio achieved by this operation? That is, by what factor is the data storage space reduced?
The cute little C program below
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint32_t compressDNA(char *a) {
// Your code goes here.
}
char* extractDNA(uint32_t u) {
// Your code goes here.
}
int main(int argc, char **argv) {
char *a = "CAAAGAGAATCCTCTT";
uint32_t compressed = compressDNA(a);
printf("%u\n", compressed);
uint32_t u = 3369383197;
char *extracted = extractDNA(u);
printf("%s\n", extracted);
free(extracted);
return 0;
}shall print out the following two lines.
1082668511
TAGATCCAGTCCACTC
Note that the unsigned integer 1082668511 is 01000000100010000011010111011111 in binary. The correspondence is such:
01000000100010000011010111011111
C A A A G A G A A T C C T C T T
Note that the unsigned integer 3369383197 is 11001000110101001011010100011101 in binary. The correspondence is such:
11001000110101001011010100011101
T A G A T C C A G T C C A C T C
Part A. In our solution, we iterate through the char array, one nucleobase at a time. We select the appropriate two bits to which the nucleobase corresponds, shift them to the appropriate position, and bitwise-OR them with the unsigned integer u to set the appropriate two bits in u. After sixteen such iterations, we will have a fresh and ready-to-go unsigned integer to return. A few observations:
- On data types. Because we're only operating on bit sequences, it actually doesn't matter a whit whether we use unsigned or signed integer types. For consistency, we use
uint32_tfor bit sequences andintfor other affairs like counters. Do recall that an expression involving a mix of signed and unsigned integers yields an unsigned result. - The last
break;in theswitchstatement, is, of course, optional. - Another possible solution is to "load" the new bits into the least significant bits of
uand left-shiftuby two places in every iteration. - The "loading" operation can also be performed by an addition;
u = u + bitsis just as correct asu = u | bits. In general, though, arithmetic operations are more expensive than bitwise operations.
uint32_t compressDNA(char *a) {
uint32_t u = 0;
int i;
for (i = 0; i < 16; i++) {
uint32_t bits;
switch (a[i]) {
case 'A':
bits = 0;
break;
case 'C':
bits = 1;
break;
case 'G':
bits = 2;
break;
case 'T':
bits = 3;
break;
}
bits = bits << (30 - (2 * i));
u = u | bits;
}
return u;
}
Part B. In our solution, we extract bits two at a time. We can accomplish this by bitwise-ANDing our argument against a bit mask. To extract the most significant two bits, we apply the mask 3 << 30, or 11000000000000000000000000000000, to eliminate everything but the most significant two bits. We then right-shift it by thirty places to bring it into the range [0, 3] for our switch statement. After every iteration, we left-shift u by two places to bring the next two most significant bits into the limelight. A few observations:
- Note the use of
mallocin the first line.malloc(17)reserves 17 bits in sequence. Why not 16? C-strings are null-terminated, and we can't neglect that zero byte. Hence also the penultimate line,a[16] = '\0'. - The discussion on data types from Part A applies identically here.
- The last
break;in theswitchstatement, is, of course, optional.
char* extractDNA(uint32_t u) {
char *a = malloc(17);
uint32_t mask = 3 << 30;
int i;
for (i = 0; i < 16; i++)
{
uint32_t base = (u & mask) >> 30;
switch (base) {
case 0:
a[i] = 'A';
break;
case 1:
a[i] = 'C';
break;
case 2:
a[i] = 'G';
break;
case 3:
a[i] = 'T';
break;
}
u = u << 2;
}
a[16] = '\0';
return a;
}
Part C. 4.
This is an exercise in the standard sizes of various primitive data types. An unsigned 32-bit integral data type like uint32_t is, of course, 32 bits, or 4 bytes long. A char is 1 byte long. The compression operation reduces 16 bytes of information to 4 bytes of storage space. Hence, we have a compression ratio of 16 / 4 = 4.
Contributed by Yujing Fan.
Go through the following assembly code, what would be stored in %rax after the execution of movq? What would be stored in %rax after the leaq? Assume %rdi
initially stored value $5 and the value stored at address 5 is 67, the value stored at address 10 is 100.
movq (%rdi, %rdi) %rax
leaq (%rdi, %rdi), %rax
Contributed by Miranda Ku.
Match the following C code snippets to their corresponding x86-64 ASM.
1.
int func_1(int x, int y, int z) {
return x+y;
}
2.
int func_2(int x, int y, int z) {
return !x^y;
}
3.
int func_3(int x, int y, int z){
return (x > y) ? z : y;
}
4.
int func_4(int x, int y, int z) {
return x >> z ? x : y;
}
5.
int func_5(int x, int y, int z) {
while (x != 0) {
x = x >> z;
}
return y;
}
6.
int func_6(int x, int y, int z) {
while (x > y) x = x >> z;
return (x > z) ? x : y;
}A.
.L0:
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L1
movl -12(%rbp), %eax
jmp .L2
.L1:
movl -8(%rbp), %eax
.L2:
popq %rbp
ret
B.
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
movl -8(%rbp), %eax
movl -4(%rbp), %edx
addl %edx, %eax
popq %rbp
ret
C.
.L0:
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
jmp .L1
.L2:
movl -12(%rbp), %eax
movl %eax, %ecx
sarl %cl, -4(%rbp)
.L1:
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jg .L2
movl -4(%rbp), %eax
cmpl -12(%rbp), %eax
jle .L3
movl -4(%rbp), %eax
jmp .L4
.L3:
movl -8(%rbp), %eax
.L4:
popq %rbp
ret
D.
.L0:
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
jmp .L1
.L2:
movl -12(%rbp), %eax
movl %eax, %ecx
sarl %cl, -4(%rbp)
.L1:
cmpl $0, -4(%rbp)
jne .L2
movl -8(%rbp), %eax
popq %rbp
ret
E.
.L0:
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
movl -12(%rbp), %eax
movl -4(%rbp), %edx
movl %eax, %ecx
sarl %cl, %edx
movl %edx, %eax
testl %eax, %eax
je .L1
movl -4(%rbp), %eax
jmp .L2
.L1:
movl -8(%rbp), %eax
.L2:
popq %rbp
ret
F.
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
cmpl $0, -4(%rbp)
sete %al
movzbl %al, %eax
xorl -8(%rbp), %eax
popq %rbp
ret
- B
- F
- A
- E
- D
- C
Jun Kai Ong.
Suppose we have the following C++ code.
unsigned int u = 25;
int a = 50;
std::cout << u - a << std::endl;
(a) What is the output ?
(b) Suppose we check the integer type for a, would it show up as an int or an unsigned int ? Explain your answer.
(a) 2^32 - 25 (4294967271)
Why not 2^32 - 26 ? -1 overflows to 2^32 -1. Hence, we can derive a general formula for an arbitrary unsigned integer, a which is -a = 2^32 - a.
(b) int
The type of the variable stored in memory does not change when the expression is evaluated, it is merely converted to an intermediate unsigned integer during the operation to match the unsigned integer on the left.
Contributed by Tyler Lindberg.
Given an array of integers of odd length, you know that every integer in the array will have an equivalent pair except one. Give a method for finding the one integer without a pair. You are not allowed to use any additional data structures and can only traverse through the array a single time. ( O(n) Runtime Complexity ) You are allowed to modify elements in the array.
Given Code:
int findUnique(int a[], int size);
Input : 2, 3, 4, 2, 3 Output: 4
Input : 1, 1, 2, 5, 3, 2, 3 Output: 5
If you solution would benefit from a textual description, put that here. If you only want to provide the code, then remove these sentences!
int findUnique(int a[], int size) {
// By XOR'ing every element in the array with the first element,
// all equivalent elements will cancel each other out and the only element
// remaining in the first spot will be the unique integer.
for (int i = 1; i < size; i++) {
a[0] ^= a[i];
}
return a[0];
}Contributed by Ayush Rath.
Create a function to determine the absolute value of a number using only bitwise operators and integer addition.
int absval(int x) {
int y = x >> 31;
// y = 0b111...111 if x negative, 0b000..0000 otherwise
int z = (x ^ y);
// z = ~x if x is negative, z = x if x non-negative
// z - y = x if x is positive
// ~x + 1 == -x -> ~x = -x+1
// z - y = -x + 1 - 1 if x is negative
// since we cannot subtract, use z + (~y + 1) to determine the absolute value
return z + (~y + 1);
}Contributed by Lucas Tecot.
Reverse the bits of an integer.
To do this, we go one by one for each bit. We shift the result int left, set its least significant to that of the original number, then shift the original to the right.
int reverseBits(int n) {
if (n == 0)
return 0;
int result = 0;
for (int i = 0; i < 32; i++) {
result <<= 1;
if ((n & 1) == 1)
result++;
n >>= 1;
}
return result;
}Contributed by Bibek Ghimire.
Write a function that is vulnerable to a buffer overflow attack and explain why/how it is vulnerable and how to fix it.
The following function is vulnerable to a buffer overflow attack because C autmoatically allots a certain amount of space (+ padding) for the buf variable. As the assembly code shows, this amount is 24 bytes in this situation.
A hacker could enter an "attack string" that takes up 20 bytes followed by an address to a malicious function of their choice. As a result, the program would return from gets() to that new function instead of going back to getAttacked().
This issue can be resolved by using fgets() instead of gets(). The former includes protections against buffer overflow attacks.
void getAttacked() {
char buf[4];
gets(buf);
// more code
}// The assembly code may look like
getAttacked:
subq $24, %rsp
movq %rsp, %rdi
call gets
Contributed by Eric Tan.
Processes and threads are similar in that they are both sequences of execution. What are the differences between the two, and what are the advantages and disadvantages?
Different processes have different address spaces, while different threads in the same process share the same address space. Thus, communication between threads requires little work since they both have access to shared data structures and variables, while interprocess communication is relatively expensive and requires use of system calls. However, since threads share an address space, an error in one thread can potentially cause errors in the other threads, whereas an error in one process won't affect another independent one. Threads are less expensive to create than processes, so it would be appropriate to use threads when you want multiple computations on some related task, whereas a process might be more appropriate if you want to do tasks that are widely different from each other or require more intensive computation.
Contributed by Caroline Quigg.
You are given two integers, n and m, as well as two indices i and j.
Write a function that inserts m into n, so that m starts a index j and ends at index i. You can ignore leading zeros of m. You can assume that the indices you are given are such that there is enough room to fit all of m.
Input n = 10001000, m = 0101, i = 1, j = 6
Output n = 10001010
The approach to this problem is as follows:
First clear the bits i through j in n
Shift m so that it lines up with i through j
Merge the two
The process of clearing the bits will involve creating a bit mask so that all bits EXCEPT i through j are covered.
int mergeBits(int n, int m, int i, int j) {
// create sequence of all 1s
int ones = ~0;
// create mask for bits in between i and j
// create mask for the bits after j
int after_j = ones << (j+1);
// create mask for bits before i
int before_i = ones << ((1 << i) -1);
int mask = before_i | after_j;
// clear bits between i and j
int clear = n & mask;
// shift m bits into position
int shifted = m << i;
return clear | shifted;
}Contributed by Hye Won (Helen) Lee.
Write a constant time function using bitwise operators to return true if a number is a power of 2 and return false if it isn't.
bool isPowerOfTwo(int n) {
if ((n == 0) || (n < 0)) return false;
return ((n&(n-1)) == 0);
}Contributed by Nikhil Kansal.
Write a function to return whether or not a function is a power of 4. This must be done in constant time (no loops, recursion, go-to, additional functions, library functions, etc.). You can use interger constants and a maximum of 8 of the following operations:
+ - ! ^ & | << >> && || == !=
Your function should fill the following function declaration:
/**
* Write a function to return 1 if a number is a power of four, and 0 if not.
* You may not use loops, recursion, goto, library or helper functions, etc.
* The function must run in constant time.
*
* You can use a maximum of 8 of the following operations:
* + - ! ^ & | << >> && || == !=
*
* You can also use integer constants.
*/
int isPowerOfFour(unsigned int x) {
/**
* implement the body of this function
*/
}The following statements should evaluate to true.
isPowerOfFour(0) == false;
isPowerOfFour(1) == true;
isPowerOfFour(2) == false;
isPowerOfFour(4) == true;
isPowerOfFour(1073741824) == true;
If you solution would benefit from a textual description, put that here. If you only want to provide the code, then remove these sentences!
int isPowerOfFour(unsigned int x) {
return ((x & (x - 1)) == 0) && ((x & 0x55555555) != 0);
}Contributed by Michael Germano.
Write a function to swap two input integers (passed by reference) in place. This swap should be done with no additional space (no temporary integers) and using only bitwise operators.
void swap(int &a, int &b) {
if (&a == &b) return; // Needed, or else "a ^= b", a.k.a. "a ^= a" will make both a and b always 0.
a ^= b;
b ^= a;
a ^= b;
}To see how this works let's look at an example using a = 15, and b = 6.
a in binary is 1111.
b in binary is 0110.
First we set a = 1111 ^ 0110 = 1001. Next we set b = 0110 ^ 1001 = 1111. Finally we set a = 1001 ^ 1111 = 0110.
The if check
Contributed by Shirley He.
Fill in the blanks of the C code. The assembly code and the memory status for the C code are given as follows. Assembly code:
08048430 <foo>:
8048430: push %ebp 8048454: mov %ecx,%eax
8048431: mov %esp,%ebp 8048456: or %edx,%eax
8048433: push %ebx 8048458: jmp 804846f <foo+0x3f>
8048434: mov 0x8(%ebp),%ebx 804845a: mov %esi,%esi
8048437: xor %eax,%eax 804845c: mov %ecx,%eax
8048439: cmp $0x4,%ebx 804845e: xor %edx,%eax
804843c: mov 0xc(%ebp),%ecx 8048460: jmp 804846f <foo+0x3f>
804843f: mov 0x10(%ebp),%edx 8048462: mov %esi,%esi
8048442: ja 804846f <foo+0x3f> 8048464: mov %ecx,%eax
8048444: jmp *0x8048500(,%ebx,4) 8048466: not %eax
804844b: nop 8048468: jmp 804846f <foo+0x3f>
804844c: mov %ecx,%eax 804846a: mov %esi,%esi
804844e: and %edx,%eax 804846c: lea (%edx,%ecx,1),%eax
8048450: jmp 804846f <foo+0x3f> 804846f: mov (%esp,1),%ebx
8048452: mov %esi,%esi 8048472: leave
8048473: ret
Memory information given by gdb:
> gdb foo
(gdb) x /8w 0x8048500
0x8048500 : 0x0804844c 0x08048454 0x0804845c 0x08048464
0x8048510 : 0x0804846c 0x00000000 0x00000000 0x00000000`
C code:
int foo(int op, int a, int b)
{
int result = 0;
switch (op){
case 0: ______________ ;
case 1: ______________ ;
case 2: ______________ ;
case 3: ______________ ;
case 4: ______________ ;
}
return result;
}int foo (int op, int a, int b)
{
int result = 0;
switch (op){
case 0: result = a & b; break;
case 1: result = a | b; break;
case 2: result = a ^ b; break;
case 3: result = ~a ; break;
case 4: result = a + b; break;
}
return result;
}Contributed by William Shao.
Consider an 8-bit IEEE floating point representation with a leading sign bit, four exponent bits, and three fraction bits.
What is the bias of our 8-bit floating point?
Write the binary representations of the following:
- Smallest positive number
- Largest denormalized number
- Smallest normalized number
- Decimal value of one
- Largest normalized number
- Infinity
Write your number with sign, followed by exponent bits, followed by fraction bits.
For example, the number 0:
0 0000 000
Bias is 2^(k-1) - 1 where k is the number of exponent bits. So for our 8-bit floating point with four fraction bits, we have a bias of 2^(4-1) - 1 = 8-1 = 7.
-
The smallest positive number will be a denormalized number with just a single bit in the fraction. This gives us:
0 0000 001 -
The largest denormalized number has all zeroes in the exponent and all ones in the fraction:
0 0000 111 -
The smallest normalized number has no fraction and a one in the exponent to make it normalized.
0 0001 000 -
To get a decimal value of one, we should have no fraction and a exponent value that gives us
2^0. Since our bias is 7, we need the exponent bits to hold 7:0 0111 000 -
The largest normalized number will have a full fraction bit sequence and normalized bit sequence. However, if we fill our normalized bits with all ones we get a special case (
infinityorNaN). So the highest exponent bit sequence that remains a normalized number is all ones minus one:0 1110 111 -
Infinity is represented by all ones in the exponent bits and a zero fraction bit sequence:
0 1111 000
Contributed by Richard Yu.
What decimal number does the 4 byte floating point binary number: 00111111011100000000000000000000 represent?
(-1)^S*M*(2)^E
Floating point numbers are encoded as S Exp Frac S = 0 so the number is positive
Bias = 127
Exp = Bias + E = 126
E = -1
M = 1 + 1/2 + 1/4 + 1/8 = 15/8
number = (-1)^0 * (15/8) * (1/2) = 15/16
Contributed by Gopi Suresh.
Write a function numSetBits that, given an unsigned integer, returns the number of set bits (1's) in that integer.
The 32-bit integer 11 has binary representation 00000000000000000000000000001011 so the function call numSetBits(11u) should return 3.
int numSetBits(unsigned int num) {
int count = 0;
while (num >0) {
count += num%2;
num/=2;
}
return count;
}Contributed by Jerry Liu.
The IEEE-754 standards require floating point to have two special values: Inf and NaN. However, your professor thinks that the program should trap instead of continuing calculation when values are Inf or NaN. Do you agree with your professor or not? Why?
This is an open-ended, Eggertisque question. The default behavior of this standard: when we encounter values of Inf and NaN, we continue.
-
Pros
1. Only a part of the program that are infected by `Inf` and `NaN` will be affected. For example, if we have a weather forecast website, we don't want the whole website to crash when only a small town has data with `Inf` or `NaN`. 2. It gives programmer the choice to whether continue the program or to throw an exception. The caller can decide what to do when it sees a floating point special value. -
Cons
1. Harder to notice bugs. In numeric applications, `Inf` and `NaN` should never happen. If the program don't trap right away, developers may never notice incorrect calculations / values. In the weather forecast website's case, if there is only a small county's data incorrect, people outside that county may never notice the anomaly of that county's data. 2. Harder to locate bugs. it might take ages for the developer to find out where exactly this value is produced. They may have to go through a lot of functions and watch a lot of variables to locate the bug. They can throw exceptions when they encounter special values if they want, but the implementation is also tedious.
© 2017 UCLA UPE Tutoring Committee.