'Study/Computer Science'에 해당되는 글 3건

  1. 2008.07.07 [Study] Understanding XOR operation
  2. 2007.02.07 [Study] Ascending Stack Vs. Descending Stack
  3. 2007.01.08 [Study] Full Stack Vs. Empty Stack

[Study] Understanding XOR operation

Study/Computer Science 2008.07.07 15:06

[[ blog 이사 과정에서 정확한 posting날짜가 분실됨. 년도와 분기 정도는 맞지 않을까? ]]

XOR and minus seems to be about the same in concept, because, as if "A-B" means "difference between A and B", A^B also means "bitwise difference between A and B".

Let's see following two SWAP algorithm. (Analysing following alogrithm will be helpful to understand difference of concept between 'A-B' and 'A^B').

add swap
*x = *x + *y;
*y = *x - *y;
*x = *x - *y;

xor swap
*x ^= *y;
*y ^= *x;
*x ^= *y;

We should focus on that both of '-' and XOR are operation to get "difference".
('-' is difference of number and XOR is bitwise difference. But, those are all "difference"!)
So, we can implement swap operation with both '-' and "XOR".

Here is conceptual description of XOR swap.
*x ^= *y; "Store difference of 'original x' and 'original y'"
*y ^= *x; "We know difference of 'original x' and 'original y'(x). So, we can get 'original x' with 'original y' and store it into 'y'."
*x ^= *y; "We know difference of 'original x' and 'original y'(x), and 'orignal x'(y). So, we can get 'original y' and store it into 'x'."

Understanding something is "Understanding it's basic concept". It's very important.!!

So, someone who understands XOR, should be able to infer "swap with XOR" at the moment of knowing about "swap with '+/-'"

신고

'Study > Computer Science' 카테고리의 다른 글

[Study] Understanding XOR operation  (0) 2008.07.07
[Study] Ascending Stack Vs. Descending Stack  (0) 2007.02.07
[Study] Full Stack Vs. Empty Stack  (0) 2007.01.08
tags : XOR
Trackback 0 : Comment 0

[Study] Ascending Stack Vs. Descending Stack

Study/Computer Science 2007.02.07 15:09

[[ blog 이사 과정에서 정확한 posting날짜가 분실됨. 년도와 분기 정도는 맞지 않을까? ]]

Ascending Stack : The stack grows upwards, starting from a low address and progressing to a higher address.
Descending Stack : The stack grows downwards, starting with a high address and progressing to a lower one.

Fundamentally, these two are same. But, I prefer descending stack, because when stack is broken, mostly post-stack-section(higher memory address) tends to be broken. So,

- [case1 : current stack has enough free space]
Descending stack is better to detect stack-corruption than ascending stack.

void func_test(void)
{
    (omitted...)
    char a[10]; // ---(*1)
    (omitted...)
    memcpy(a, data, len); // len > 10 ---(*2)
   (omitted...)
}

If stack space after (*1) is not used, then even if stack is corrupted, it is very difficult to detect in ascending stack.
(because, no one uses corrupted area.) So, debugging is more difficult.

- [case2 : current stack is almost pull]
In descending stack, usually, corrupting stack of specific thread(Thread A) affects it's own behavior firstly. So, it is easier to debug - same with [case1].
In ascending stack, corrupting stack may affects to other thread's stack - thread whose stack is just next (higher address) of Thread A - firstly with high possibility (especially, if several stacks are adjacent in memory space). This usually leads to debugging-nightmare

신고

'Study > Computer Science' 카테고리의 다른 글

[Study] Understanding XOR operation  (0) 2008.07.07
[Study] Ascending Stack Vs. Descending Stack  (0) 2007.02.07
[Study] Full Stack Vs. Empty Stack  (0) 2007.01.08
tags : Stack
Trackback 0 : Comment 0

[Study] Full Stack Vs. Empty Stack

Study/Computer Science 2007.01.08 15:08

[[ blog 이사 과정에서 정확한 posting날짜가 분실됨. 년도와 분기 정도는 맞지 않을까? ]]

Stack can be classified into "Full Stack" and "Empty Stack" by addressing mode.

Full Stack : The stack pointer points to the last item in the stack.
Empty Stack : The stack pointer points to the next free space on the stack.

I prefer Empty Stack because... how can I say... It is more computer-like-expression.... :-)
Usually, in computer science, indexing starts like (i=start) and ends like (i<end)... That is, [a, b) range concept is normal...
In Empty Stack, we can say "Stack is empty" by checking (SP == Framebase). And this is more suitable for above concept...

신고

'Study > Computer Science' 카테고리의 다른 글

[Study] Understanding XOR operation  (0) 2008.07.07
[Study] Ascending Stack Vs. Descending Stack  (0) 2007.02.07
[Study] Full Stack Vs. Empty Stack  (0) 2007.01.08
tags : Stack
Trackback 0 : Comment 0

티스토리 툴바