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)
001011
OR
101111
= 101111
to check if the second bit is 0
Bitwise AND,
&(ampersand); (logical AND, && in C)
001011
AND 001000
= 001000
to check if the third bit is 1
Bitwise XOR,
^ in C;
0010
XOR 1010
= 1000
used to manipulate bit patterns
representing sets of Boolean variable
Bit shifts
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)
Examples:
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)
{
n^=(1<<i);
n^=(1<<j);
}
return n;
//If two bits are different, we just need to flip those two bits
Count number of binary 1s in a number
int nos_of_ones(int
n){
int count = 0;
while (n!=0){
if (n&1){
count++;
}
n>>1;
}
return (count);
}
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)
Memory Layout
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
and deactivated.
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).