Computer Science Notes For DSP Engineers
From Gracenote/ Qualcomm/ Apple/ Palm Technical Interview
1. Bitwise operations tricky related
On modern older microprocessor architectures, bitwise operations are generally the same speed as addition, though still faster than multiplication and division operations
Bitwise NOT, or complement, ~ in C; (logical NOT, Boolean, ! in C)
Bitwise OR, | in C; (logical OR, || in C)
to check if the second bit is 0
Bitwise AND, &(ampersand); (logical AND, && in C)
to check if the third bit is 1
Bitwise XOR, ^ in C;
used to manipulate bit patterns representing sets of Boolean variable
Arithmetic shift: suitable for signed two¡¯s complement binary numbers
Logical shift: suitable for unsigned binary numbers
Circular shift: rotate
<< or >> in C++; (*2^n or /2^n)
You have an eight bit multiply operator that takes two 8 bit numbers and returns a 16 bit value. Given two 16 bit values stored in 32 bit int variables, find the product using the 8 bit multiply operator.
int multiply8bit(int m, int n)
int mLow_nLow = (m & 0x00FF) * (n & 0x00FF);
int mHigh_nLow = ((m & 0xFF00)>>8) * (n & 0x00FF);
int mLow_nHigh = (m & 0x00FF) * ((n & 0xFF00)>>8);
int mHigh_nHigh = ((m & 0xFF00)>>8) * ((n & 0xFF00)>>8);
return mLow_nLow + (mHigh_nLow<<8) + (mLow_nHigh<<8) + (mHigh_nHigh<<16);
Swap bits in position i and j for a number
if (( (n&(1<<i))>>i)^((n&(1<<j))>>j)
//If two bits are different, we just need to flip those two bits
Count number of binary 1s in a number
int count = 0;
Reverse the bit representation of an integer questions abt stack/heap/recursion etc.
//XOR with all 1s
10110001 XOR 11111111 = 01001110
1. Memory Layout (Where are Global, Static and Local Variables allocated in the memory?)
Global and Static variables: Stored in BSS (Block Started by Symbol) section of the data segment. (static memory area)
Local variables: Stored on the stack and are valid until the program exits from the function in which they are defined. (dynamic memory area- STACK)
Static Local variables: Static variables in a function, for example, are initialized just once while compiling. Default is 0. We could use static local variables to compute nth factorial, because it will
not free the static n after calling the function each time. It will remain in the static memory area until the program ends.
Static Global variables: only valid in the modular file where they are defined, so that hidden from other modular. (The scope/visibility is limited to that particular file)
Load and store operations copy the bit pattern from the source into the destination. The source (register or memory) does not change. Of course, the pattern at the destination is replaced by the pattern at the source.
Memory is built to store bit patterns. Both instructions and data are bit patterns, and either of these can be stored anywhere in memory (at least, so far as the hardware is concerned.) However, it is convenient for programmers and systems software to organize memory so that instructions and data are separated. At right is the way MIPS operating systems often lay out memory.
Although the address
space is 32 bits, the top addresses from 0x80000000 to 0xFFFFFFFF are not
available to user programs. They are used for the operating system and for
The parts of address space accessible to a user program are divided as follows:
Text Segment: This holds the machine language of the user program (the text).
Data Segment: This holds the data that the program operates on. Part of the data is static. This is data that is allocated by the assembler and whose size does not change as a program
executes. Values in it do change; "static" means the size in bytes does not change during execution. On top of the static data is the dynamic data. (HEAP), this is data
that is allocated and deallocated as the program executes. In "C" dynamic allocation and deallocation is done with malloc() and free(). (calloc() and realloc())
The return values of these allocation functions are the initial address of the allocated memory. (values of pointer variables)
Stack Segment: At the top of user address space is the stack. With high level languages, local variables and parameters are pushed and popped on the stack as procedures are activated
2. Terminology & Trivia
Volatile: A variable or object declared with the volatile may be modified externally from the declaring object. Variables declared to be volatile will not be optimized by the compiler because the computer must assume that their values can change at any time.
Memory operation: memmove() and memcpy() (coming soon¡)
Process V.S. Threads
Process is an instance of a program (needs executable). Thread is an execution of a C-function. A process has its own address space, heap, code memory, data memory, global memory. Each thread has its own stack, thread specific variables, thread context (such as registers, program counter). Memory space of one process does not overlap with that of other process. A process can contain multiple threads. All the threads within a process share the process's memory space. If a thread changes a global variable (memory), other threads accessing global variable will read updated value. Thus, inter-task communication is simpler. The inter-task context switching has less overhead. Whereas, inter-process context switching has more overhead. There is no hierarchy among threads within same process (parent-child-grand child hierarchy).