Search results for 'programming/programming interview'

  1. 2011.10.01 -- C언어 다시 정리
  2. 2011.03.23 -- Counting ones
  3. 2011.03.22 -- big-endian and little-endian
  4. 2011.03.21 -- 지식 기반 문제
  5. 2011.01.09 -- bit operations 총 정리
  6. 2009.12.17 -- Saturation arithmetic
  7. 2009.12.15 -- AND & XOR

C언어 다시 정리

2011.10.01 16:36
정잘 기억을 못하는 부분에 대해서만 정리를 해본다. 

1. 비트연산 정리
참고: http://kenshin579.tistory.com/entry/bit-operations-%EC%B4%9D-%EC%A0%95%EB%A6%AC

2.scanf & printf

%8d   : 8칸 학보하고 오른쪽 정렬해서 출력함
%-8d  : 8칸 학보하고 왼쪽 정렬해서 출력함
%+8d  : %8d방식과 같으며 앞에 부호(+,-)를 붙여서 출력함


3. 조건 연산자 (삼항 연산자)
조건이 true인 경우에 A를 반환하고 아니면 B를 반환한다.
조건 ? A : B n

x = (y < 0)? 10 : 20;

4. pointer와 배열
- 주소를 담는 pointer에 type이 필요한 이유는 변수를 참조할때 몇 바이트만큼 읽어야 할지를 결정하기 위해서 필요하다. 

- 배열이름 (ex. array[5]={1,2})도 상수 포인터이고 첫번째 요소의 주소값을 가리킨다. 
int a[5] = {1,2,3,4,5}
printf ("%d  = %d\n", a[2], &a[2]); // 같다.

- 문자열 상수
char str1[15]  = "abcd"; // 문자열 변수
char *str1 = "abcd";       // 이건 문자열 상수이기 때문에 변경이 불가능하다.

- 배열을 인자로 전달하는 방법
* 둘다 완전히 같은 뜻이다. 
1. int func(int *pArr)
2. int func(int pArr[])

- 포인터와 const 키워드
1. 데이터 상수화 : 포인터 p가 가리키는 변수의 값을 못 바꾸게 하겠다는 뜻
int a = 10;
const int* p = &a; // 포인터 p를 통해서 변수 a의 값을 변경하는 것만 막겠다.
*p = 30; // Error!
a = 30 // OK

2. 포인터 상수화 : 포인터 p가 지니는 주소 값을 변경 할 수 없다는 뜻
int a = 10;
int b = 20;
int* const p = &a;
p = &b; // Error!
*p = 30; // OK

- 다차원 배열 개념
초기화하는 방법은 다음과 같다. 
int array[3][3] = {
 {1, 2, 3},
 {4, 5, 6},
 {7, 8, 9}
};

int array[3][3] = {1, 2, 3, 4, 5, 6, 7}

int arr[][] = {1,2,3,4,5,6,7,8,9} // Error!!!
int arr[][4] = {1,2,3,4,5,6,7,8} // 2 x 4

- 2차원 배열 & 포인터 연산
NOTE: arr[i] == arr + i

int arr[2][4];

printf("arr : %d arr[0]\n", arr, arr[0]);
printf("arr +1 : %d arr[1]\n", arr+1, arr[1]);

int (*pArr)[4]; // pArr는 int arr[2][4] or arr[3][4]와 같은 배열을 가리킬 수 있는 배열 포인터이다. 
*여기서 [4]의 의미는 4칸씩 건너 뛴다고 보면 된다.
ex. void show_data(int (*ptr)[4], int a);

void show_data(int (*ptr)[4], int a) == void show_data(int ptr[][4], int a);
int ptr[][4]; // 변수 선언으로는 안됨!!!

- 간단한 포인터 복습
int a[3][2] = { {1, 2}, {3, 4}, {5, 6}};

(*(a+1))[0] = ??
*(a[1]+2) = ??
*(*(a+2)+1) = ??

다음은 왜 서로 같은지 증명하시오. 
int a[10][10];
1. a[i][j]
2. *(a[i]+j)
3. (*(a+i))[j]
4. *(*(a+i)+j)

- 함수포인터 : 메모리상에 존재하는 함수의 위치를 가르키는 포인터
* 가상함수라고 보면 쉽게 이해할 수 있을 것이다.

함수 포인터선언
int fct1(int a); int fct2(double a, double b);
int (*fPtr1)(int); int (*fPtr2)(int, int);
fPtr1 = fct1;
fPtr2 = fct2;
fct1(a);

- 함수 포인터는 언제 많이 사용할까요?

- 입출력 
1. character 
int ch;
getchar(ch); // fgetc(stdin);
putchar(ch); // fputc(ch, stdout);

2. string 
char str[10];
gets(str); // fgets(std, sizeof(str), stdin);
* gets의 경우 overflow가 될 경우 abort가 일어나지만, fgets는 

puts(str); // fputs(str, stdout):
*차이점: puts함수는 문자열을 출력한 다음에 자동으로 줄을 바꿔주지만, fputs는 자동으로 바꿔주지 않는다. 

- 구조체
ㅁ. 선언 & 초기화
방법1.
struct point {
  int x;
  int y;
}; 

int main() {
struct point p1;

방법2.
struct point {
  int x;
  int y;
} p1, p2;

접근.
p1.x = 10;
p2.y = 15;

struct person {
   char name[20];
   char phone[20];
   int age;
};

초기화.
struct person person1 = {"Frank Oh", "02-123-1234", 20};
struct person person2 = {.name="Frank Oh", .phone="02-123-1234", .phone=20];

ㅁ. 구조체 및 배열
배열 선언 및 초기화.
struct person pArray[3] = {
  {"Frank Oh", "02-123-1234", 20},
  {"Angela Oh", "02-123-1234", 25},
  {"David Oh", "02-123-1234", 25}
};

접근.
printf("%s %s %d", pArray[0].name, pArray[0].phone, pArray[0].age);

ㅁ. 구초제 및 포인터
선언.
struct person *pMan;

접근 (2가지).
1. printf("name: %s", (*pMan).name);
2. printf("name: %s", pMan->name);

ㅁ. 구조체 함수에서의 전달 및 리턴 
struct simple {
 int data1;
 int data2;
};

int main() {
 struct simple s_data = get_data(); // struct 구조체에서는 = assign가 가능하다
 show_data(s_data);
 swap_data(s_data);
 show_data(s_data);
}

매개 변수 (call-by-value, call-by-reference).

void show_data(struct simple ds) {
  printf("%d %d", ds.data1, ds.data2);
}

void swap_data(struct simple *ds) {
 int temp = ds->data1;
 ds->data1 = ds->data2;
 ds->data2 = temp;
}

리턴. 
struct simple get_data() {
 struct simple temp;
 printf("Enter two numbers: ");
 scanf("%d %d", &temp.data1, &temp.data2);
 return temp;
}

ㅁ. typedef 사용예 (2가지 방법)
선언.
struct data {
  int x;
  int y;
};
typedef struct data Data;

// ------------------
typedef struct data {
   int x;
   int y;
} Data;

Data s_data;

ㅁ. union과의 차이점
union : 서로 다른형의 변수를 하나의 메모리 공간에서 공유하는 경우에 사용된다. 
union data {
   int d1;
   double d2;
   char d3;
};

union은 언제 잘 사용할까요?
Ex. icmp header의 type에 따라서 데이터 section에 채워지는 부분이 다른데 이 부분을
union으로 선언하여 type에 따라서 다르게 해석하면 된다. 

struct icmphdr {  

  u_int8_t type;                /* message type */  

  u_int8_t code;                /* type sub-code */  

  u_int16_t checksum;  

  union  {    

    struct    {      

       u_int16_t id;      

       u_int16_t sequence;    

    } echo;                     /* echo datagram */    

    u_int32_t   gateway;        /* gateway address */    

    struct    {      

       u_int16_t __unused;      

       u_int16_t mtu;    

     } frag;                   /* path mtu discovery */  

  } un;

};


struct icmphdr *p;
p->un.echo.id; // 접근

참고
1. http://kldp.org/node/22864
2. http://paulownia.egloos.com/4366254

ㅁ. enum 사용법
* 그냥 number대신 이름으로 사용하는 것임. 
enum color {RED=1, GREEN=2, BLUE};
color lcd_screen;

lcd_screen=RED;

구조체는 언제 사용하면 좋을까요? 
1. 여러 type의 데이터를 하나의 구조로 관리하기 때문에 데이터 manipulate이 쉬워진다. 
2. 함수에서 return할 수 있는 type은 하나지만, struct를 사용해서 여러 가지 type을 리턴할 수 있다. 

- 파일 입출력
파일 개방 모드 = 파일 접근 모드 (r, w, a, r+, w+, a+) + 데이터 입출력 모드(text or binary)
+가 붙으면 읽기 쓰기가 동시에 가능해지고 +의 의미는 파일이 존재하는 경우에만 차이가 있다. 

ㅁ. 파일 입출력 예제 (open, close, writing, reading)
* including errors check as well

int main() {
 
 //writing
 FILE *file = fopen("input.txt", '"wt");
 if (file == NULL) {
   perror("Error opening file\n");
   return 1;
 }
 
 fputs("This is a test\n", file);
 fprintf(file, "Another test\n");

 int status = fclose(file);
 if (status != 0) {
  perror("Error closing a file\n");
  return 1;
 }

 // reading (skipping error checks for simplicity)
 file = fopen("input.txt", "wt");
 fgets(str, sizeof(str), file);
 printf("%s", str);
 fscanf(file, "%s", str);
 printf("%s", str);
 fclose(file);

}

ㅁ. checking return value
fgets : EOF  (-1)
fgets : NULL (0)
fscanf : EOF(-1)

리턴값을 체크할때 주의할점들을 보자. 

char ch;
fputc('1', file);
fputc((char)255, file); // -1로 변환된다. 
fputc('2', file);

while (1) {
  ch=fgetc(file);
  if (ch==-1) break; // (char)255을 읽어드리면 -1값이기 때문에 문제가 생긴다. 
}

해결책1.
char ch; ==> int ch;으로 변경해준다. 
11111111 데이터가 int형으로 변환이 되면 00000..... 111111(255)가 되지만, int 형으로 -1은 1111.....11111이기 때문이다. 

해결책2.
feof함수를 사용하는 것이다. FILE 구조체 변수를 참조하면, 파일의 끝까지 데이터를 출력했는지에대한 
정보를 알 수 있다. 

char ch;
while(1) {
  ch = fgetc(file);
  if (feof(file)!=0) break;
}

ㅁ. random access (fseek)
ex. 1234abcd56789이걸 쓰고 위치를 변경해서 읽어보고 하자. 
SEEK_SET(0) :  파일의 맨 앞으로 이동한다. 
SEEK_CUR(1) : 이동하지 않는다. 
SEEK_END(2) : 파일의 끝으로 이동한다. 

fseek(FILE *stream, long offset, int wherefrom);
offset : wherefrom에서부터 offset만큼 이동하는 값
wherefrom : 윗값 중 하나

...
fputs("1234abcd56789", file);
...
fgest(buf, 7, file); 
printf("%s\n", buf);

fseek(file, 2, SEEK_CUR);
// fseek(file, -2, SEEK_CUR);
// fseek(file, 2, SEEK_SET);
// fseek(file, -2, SEEK_END);
printf("%c\n", fgetc(file));
fclose(file);



- 메모리 동적할당

int *arr= (int*)malloc(sizeof(int)*size) == int *arr = (int*)calloc(size, sizeof(int));
차이점은 calloc은 초기화(zero)로 하지만, malloc은 하지 않는다. 

int size, i;
printf("Enter a array size: ");
scanf("%d", &size);
int *arr = (int*)malloc(sizeof(int)*size);
if (arr == NULL)
   perror("Enter allocating memory\n");

for (i = 0; i < size; i++)
   arr[i] = i+1;

for (i = 0; i < size; i++)
  printf("%d\n", arr[i]);

free(arr); 

- 매크로 함수
#define PI 3.1415
#define SQUARE(x) x*x
int a = SQUARE(2); // preprocessor에 의해서 2*2으로 치환된다. 

#define QUOTEME(x) #x // QUOTEME(3) -> "3"

#define ADD(x,y) printf("x+y = %d\n", x+y); // x+y=7로 출력된다. 
ADD(3,4);

정확하게 원하는 
#define ADD(x,y) printf(#x "+" #y "=%d\n", x+y); 3+4=7로 출력된다. 

#define CONCAT(x,y) x##y // ##는 concatenate하게 다는 의미를 갖는다. 
printf("%d\n", CONCAT(2,4));
printf("%s\n", CONCAT("Good", "Morning"); // 이건 실제로 안됨. 

- 모듈화
file.c: -> file_1.c & file_2.c
int i = 0;
int main() {
 i++;
 return 0:
}

file_1.c:
int i=0;

file_2.c:
extern int i;
int main() {
 i++;
 return 0;
}

aaa.c                                               bbb.c
static int val1;   <---- (접근 불가)       extern int val1;
int val2;           <----- (접근 OK)      extern int val2;

#ifndef, #endif를 이용한 조건부 컴파일
header를 여러 파일로 나누게 되다보면 중복되는 부분이 생기는 문제가 생긴다. 


count.h: 중복되어 컴파일 되는 것을 막게 된다. 
#ifndef _COUNT_H_
#define _COUNT_H_

int count = 0;

#endif  


References
1.Function Pointer Tutorial, http://www.newty.de/fpt/fpt.html
2.Function Pointers in C and ..., http://www.cprogramming.com/tutorial/function-pointers.html
3. 
4.








 
저작자 표시
신고

'programming > programming interview' 카테고리의 다른 글

C언어 다시 정리  (0) 2011.10.01
Counting ones  (0) 2011.03.23
big-endian and little-endian  (0) 2011.03.22
지식 기반 문제  (0) 2011.03.21
bit operations 총 정리  (0) 2011.01.09
Saturation arithmetic  (0) 2009.12.17

Frank kenshin579 programming/programming interview C, C언어 정리, C정리

Counting ones

2011.03.23 17:27

1. 주어진 정수를 2진수로 표현할 때 1로 설정된 비트의 수를 count하는 함수를 구현하기
ㅁ. 알고리즘
고려해야할 입력값: 음수, 양수
Java로 구현할 경우, logical shift (>>>)를 사용하면 오른쪽으로 shift할때 앞에 minus 부호를 고려할 필요가 없다.
하지만, C로 구현할 경우, 음수의 경우에는 ?? 시프트할때 몇번 하는지를 count했다가 quit하면 된다.

ㅁ. 구현 (Java)
Naive Implementation
Running time : O(n), n is the number of bit
 public class CountOneEx1 {

    static int numOnesInBinary(int number){
        int countOnes = 0;
        while (number != 0) {
            if ((number & 1) == 1)
                countOnes++;
            number = number >>> 1;
        }
        return countOnes;
    }

    public static void main(String[] args) {
        int num = 5;
        int count = numOnesInBinary(num);

        System.out.println("Number: " + num);
        System.out.println("CountOnes: " + count);
        System.out.println("Number: " + num);
    }

}


Better Implementation
Running time: O(m), where m is the number of ones in the integer value.
아이디어:
0111000에서 1을 빼면  가장 낮은 자리에 있는 1과 그보다 낮은 바리에 있는 모든 비트들이 바뀐다, 01101111.
so
0111 0000 AND (0111 0000 - 1) =
   0111 0000
& 0110 1111
   0110 0000

Using the above idea, we can just repeat this until the number becomes zero and just count them.
And also this version would work for the negative number in C
 public class CountOneEx2 {

    static int numOnesInBinary(int number){
        int countOnes = 0;
        while (number != 0) {
            number = number & (number - 1);
            countOnes++;
        }
        return countOnes;
    }

    public static void main(String[] args) {
        int num = 5;
        int count = numOnesInBinary(num);

        System.out.println("Number: " + num);
        System.out.println("CountOnes: " + count);
        System.out.println("Number: " + num);
    }

}


References
1.
저작자 표시
신고

'programming > programming interview' 카테고리의 다른 글

C언어 다시 정리  (0) 2011.10.01
Counting ones  (0) 2011.03.23
big-endian and little-endian  (0) 2011.03.22
지식 기반 문제  (0) 2011.03.21
bit operations 총 정리  (0) 2011.01.09
Saturation arithmetic  (0) 2009.12.17

Frank kenshin579 programming/programming interview bitCount

big-endian and little-endian

2011.03.22 17:18

1. 개념정리
endian은 바이트 값을 저장할때 시스템에서 각 바이트를 저장하는 순서를 나타내는 용어이다.

MSB -> LSB 순...
ㅁ. big-endian (MSB가 앞에 나옴)
Ex. 2 bytes, 16 bits인 정수값이 있다고 하자, A45C
A45C -> A45C

ㅁ. little-endian (LSB가 앞에 나옴)
A45C -> 5CA4

2. 시스템이 big-endian인지 little-endian인지를 판단하는 함수글 구현하라
알고리즘
num=1 (0x00 01)
big-endian : 00 01
little-endian: 01 00
  * 앞의 byte만 읽어드리면 구분할 수 있게됨

C
  #include <stdio.h>
 
- int endianness() {
|     int num;
|     char *ptr;
|
|     num = 1;
|     ptr = (char*) &num;
|     return (*ptr);
| }
 
- int main() {
|     if (endianness())
|         printf("little-endian system\n");
|     else
|         printf("big-endian system\n");
|     return 0;
| }

Using union
   #include <stdio.h>
 
- int endianness() {
|     union {
|         int theInteger;
|         char singleByte;
|     } endianTest;
|
|     endianTest.theInteger = 1;
|     return endianTest.singleByte;
| }
 
- int main() {
|     if (endianness())
|         printf("little-endian system\n");
|     else
|         printf("big-endian system\n");
|     return 0;
| }


References
1. 리틀 엔디언과 빅 엔디어, http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/Network_Programing/Documents/endian
2.
저작자 표시
신고

'programming > programming interview' 카테고리의 다른 글

C언어 다시 정리  (0) 2011.10.01
Counting ones  (0) 2011.03.23
big-endian and little-endian  (0) 2011.03.22
지식 기반 문제  (0) 2011.03.21
bit operations 총 정리  (0) 2011.01.09
Saturation arithmetic  (0) 2009.12.17

Frank kenshin579 programming/programming interview big-endian, endianess, little-endian

지식 기반 문제

2011.03.21 17:54
1. C++와 자바의 차이점을 설명하시오.
- 둘다 object-oriented language이므로 syntax상에서 보면 둘다 유사함
Java
1. 개발목표: Java: 보안, portability에 중점을 두고 개발됨
2. bytecode로 compile되고 JVM에 의해서 실행이 된다. 그래서 다른 여러 OS에서도 JVM만 있으면 실행가능하다.
3. C++#3와 달리 버그를 줄이기 위해서 메모리관리는 garbage collection으로 한다.
4. C++#4 부분은 자바에서 지원하지 않음
 * 다중 상속에 제안이 있지만, interface를 사용해서 다중상속과 비슷한 효과를 낼 수 있다. (아래 예제 참조)
5. 자동 형 캐스팅을 지원하지 않았지만, 최근버전에는 제너릭과 오토파싱 같은 기능이 추가되어 자동 캐스팅을 지원한다.
6. 자바에서는 모든 메소드가 가상메소드이다.

C++
1. 개발목표: 속도 및 C와의 compatibility issue에 중점을 두고 개발됨
2. 실제 기계어로 compile되서 실행되어 속도면에서 빠르다.
3. 프로그래머에 의해서 메모리 관리, 포인터등과 같은 기능들은 모두 수동으로 관리되어야 한다.
4. 연산자 오버로딩 (operator overloading)과 다중 상속을 지원한다.
5. 자동 형 캐스팅을 지원한다.

결론: 로우레벨 시스템 액세스라던지 아니면 속도를 고려해야 한다면 C++를 사용하는게 좋고
개발속도나 이식성을 고려한다면 Java를 사용하는게 좋다.

2. overload??

3. C++ friend class란?

4. C++ template 사용법?

5. multiple interface 예제!!!

6. 상속: B를 인자로 받는 메소드가 있다면, 어느 클래스를 그 메소드에 인자로 사용할 수 있는가?



당연히 B는 인자로 사용되고.

질무은 결국 자식이야, 부모 클래스야, 이 둘중에 하나인데...

C 클래스의 경우에는 B를 상속받기 때문에 B에 있는 모든 메소드를 가지고 있기 때문에 C도 인자로 넣길 수 있다.

A와 D는 안된다.


7, 가바지 컬렉션은 무엇이고 어떻게 구현할 수 있는지 설명하시오. 

Garbage collection은 애플리케이션에서 더 이상 쓰지 않거나 액세스할 수 없는 메모리를 자동으로 찾아서 메모리를 되찾게 해준다.

장점:

- 프로그램머가 직접 메로리관리 하지 않아도 되기 때문에 프로그램 및 인터페이스를 설계하기 가 쉬움

- no dangling reference / no memory leak problem


단점:

- 메모리를 언제 되찾아올지 결정해야 하는 오버헤드가 존재함

- requires more memory


Example (unrefereneced objects)

 Student ali = new Student();
Student khalid = new Student();
ali = khalid;
ali Object becomes a garbage!!!


Programming Tips

* Reuse objects instead of generating new ones

// this generates one million objects which leads to creating a lot of garbage.
 for (int i=0;i<1000000; ++i) {
    SomeClass obj= new SomeClass(i);
    System.out.println(obj);
}

// This is better version
SomeClass obj= new SomeClass();
for (int i=0;i< 1000000; ++i)   {
   obj.setInt(i);
  System.out.println(onj);
}


구현 방법

- reference counting

* can't handle circular reference

  ㅁ. does not move blocks



- mark and sweep

* can handle circular references

  ㅁ. does not move blocks (unelss you also compact)

- copying

  ㅁ. moves blocks


Other GC algorithms (many more)
- mark and compact

- stop and copy

- generational

- incremental (train algorithm)

- concurrent (in 1.4.2 JVM and onwards)


Q: 언제 가비지 컬렉션을 실행하나?

A: 프로그램에 할당된 메모리가 정해진 threshold 값보다 높을 경우


8. 네트워크의 성능을 따질때 중요한 두가지는? (delay, bandwidth)


9.대칭키 암호와 공개키 암호의 차이점을 설명하고 각각을 어느때에 사용하면 좋은지 간단한 예를 드시오.


10. 새로운 암호 알고리즘을 발견하면 바로 사용해야 할까?


11. 해시 테이블과 이진 검색 트리를 비교 (장단점)하시오. 그리고 제한된 PDA용 주소록에 사용할 자료 구조를 설계한다면 어느 쪽을 쓰는 것이 좋을까?


12.




References
1.

저작자 표시
신고

'programming > programming interview' 카테고리의 다른 글

Counting ones  (0) 2011.03.23
big-endian and little-endian  (0) 2011.03.22
지식 기반 문제  (0) 2011.03.21
bit operations 총 정리  (0) 2011.01.09
Saturation arithmetic  (0) 2009.12.17
AND & XOR  (0) 2009.12.15

Frank kenshin579 programming/programming interview 기본 질문, 프로그래밍 면접

bit operations 총 정리

2011.01.09 21:28
2의 보수 이진표기법
1. 개념 정리
양수일떄는 똑같고 음수일때는 Ex. -1, 0000 0001 (1)에서 complement을 하고 1을 더하면 된다. 1111 1110 + 1 = 1111 1111(-1)
그리고 2의 보수 이진표기법에서는 첫번째 비트는 부호비트이다.

2. 사용하는 이유, 덧셈, 뺄셈이 매우 간단해진다. Ex. 0000 0001(1) + 1111 1111(-1) = 0000 0000 (0) 그냥 더하면 된다.




기본 bit operations
1. ~(NOT), complement
Digits which were 0 become 1, and vice versa.
unsigned int x = 7;      // (0111)
printf ("%d\n", ~x);    // (1000) = -8

2. !(Logical NOT),  (true or false)
* this is not bitwise operation and do not confuse with NOT, the complement operation
 unsigned int x = 7;      // (0111)
printf("%d\n", !x);      // 0
printf("%d\n", !!x);      // 1

3. |(OR)
* 특정한 위치의 비트를 1로 만들때 유용하다. 
unsigned int x = 5;      // (0101)
unsigned int y = 3;      // (0011)
printf ("%d\n", x|y);   // (0111) = 7


The bitwise OR operation is used in situations where a set of bits are used as flags. Each bit in the number represent distinct boolean variable. 
 
#define OPT_CPU     0x01
#define OPT_MEM    0x02

#define DISPLAY_CPU(m)      (((m) & OPT_CPU) == OPT_CPU)
#define DISPLAY_MEM(m)     (((m) & OPT_MEM) == OPT_MEM)

unsigned int optflag = 0;
if (!strcmp(argv[opt], "-c"))
   optflag |= OPT_CPU;
else if (!strcmp(argv[opt], "-m"))
   optflag |= OPT_MEM;

// check option flag
if (DISPLAY_CPU(optflag))
   printf("CPU flag is set\n");
if (DISPLAY_MEM(optflag))
   printf("MEM flag is set\n");


4. ^(XOR)
the output is 1 if the two bits are different, and 0 if they are the same. 
비교대상이 되는 두 항의 값이 틀리면 1, 같으면 0이 되는 연산을 수행한다.
unsigned int x = 5;      // (0101)
unsigned int y = 3;      // (0011)
printf ("%d\n", x^y);   // (0111) = 7

5. &(AND)
The result is 1 if the both bits are 1. Otherwise, the result is 0.
AND 연산은 특정한 위치의 비트를 0으로 만들때 유용하다. 또한 특정한 위치의 비트가 1인지 아닌지를 알아낼때 사용한다. 
unsigned int x = 5;      // (0101)
unsigned int y = 3;      // (0011)
printf ("%d\n", x&y);   // (0001) = 1

The bitwise AND is used to perform a bit mask operation. You can think of AND operation as extracting a bit from the number or determine whether a particular bit is 1 or 0.
unsigned int x = 3;      // (0011)
unsigned int y = 2;      // (0010)
printf ("%d\n", x & y);   // (0010) = 2
We know that the second bit is 1.

6. <<, >>, >>>>(SHIFT)
C, C++, C#: <<, >>
Java, JavaScript: <<, >>, >>>
양수의 경우 <<, >> shift는 어느 언어에서던지 결과가 같다.
음수의 경우,
ㅁ. C, C++ (구현에 따라 조금씩 다를 수 있음)
10100110>>5 -> 00000101 or 11111101

ㅁ. C#
첫번째 비트를 제외하면 새로 추가된 비트는 모두 0이 된다.
10100110>>5 -> 10000101

ㅁ. Java, JavaScript
음수의 경우 무조건 빈공간을 1로 채운다
10100110>>5 -> 11111101

>>>(logical shift) 연산은 Java, JavaScript에서만 존재한다.
10100110>>5 -> 00000101


PROBLEMS
Q: 두번째 bit를 clear하는 방법? 0110(6) -> 0100(4)
A: NOT (complement) 과 AND operation을 사용한다.

~ 0010 (2)     <--- 두번째 비트, take the complement
   1101 (13)

   0110 (6) <---- clear the second bit
& 1101 (13)
--------------
   0100 (4)

Q: XOR 비트 연산은 언제 유용하게 사용할 수 있나?
A: 간단한 암호화할때 사용함. 
예로
        00001011 (11)
XOR  00001101 (13) <--- secret code. 
----------------------
        00000110 (6)
XOR  00001101 (13) <--- secret code.
--------------------
        00001011 (11) <--- original number

Q: Shift 연산은 언제 자주 사용하는가?
A: 2를 곱하거나 2로 나누는 작업을 매우 빠르게 할 수 있다.
5<<1 -> 10
0000 0101(5) -> 0000 1010(10)
10>>1 -> 5
0000 1010(10) -> 0000 0101(5)

Q:비교 연산자를 전혀 사용하지 않고 두 정수가 같은지 판단하는 함수를 만드시오.
A: (x - y) == 0

Q: XOR만으로 swap하는 방법 without using a temporary variable. 
A: 
x = x ^ y;
y = x ^ y; // y는 x 값을 갖게 된다
x = x ^ y; // x는 y의 값을 갖게 된다.
 

Q: 18개의 one을 쉽게 만드는 방법?
A: shift 연산을 사용하면 쉽게 1로 채울 수 있다.
(1<<18) -1 ==> 0x3FFFF

Q:bitParity check하는 함수를 구현하기
ex. 1001 -> 1^0^0^1 = 0 (even parity)

Q: isNonZero 함수 구현하기 without using ! operation
ex. isNonZero(3) = 1, isNonZero(0) = 0
A:
int neg_x = ~x+1; // negate the x, -x
((x|neg_x)>>31)&1

Q: isLessOrEqual를 구현하기??
A:
 
Q: x 값을 zero로 reset하는 방법?
A: x ^ x, XOR시키면 된다.  

References
1. 프로그래밍 면접 이렇게 준비한다, 한빛미디어
2. 비트연산 집대성, http://kicom95.egloos.com/1016012
5. 
저작자 표시
신고

'programming > programming interview' 카테고리의 다른 글

Counting ones  (0) 2011.03.23
big-endian and little-endian  (0) 2011.03.22
지식 기반 문제  (0) 2011.03.21
bit operations 총 정리  (0) 2011.01.09
Saturation arithmetic  (0) 2009.12.17
AND & XOR  (0) 2009.12.15

Frank kenshin579 programming/programming interview bit operation, C언어 정리, 비트연산, 프로그래밍 면접

Saturation arithmetic

2009.12.17 16:32
range (min, max)안에서 arthmetic operation 을 할때 operation 결과값이 max/min을 넘을 경우, 결과값이 saturated (포화)되는 것을 의미한다.

This is how I understand it.

References
1. http://en.wikipedia.org/wiki/Saturation_arithmetic
저작자 표시
신고

'programming > programming interview' 카테고리의 다른 글

Counting ones  (0) 2011.03.23
big-endian and little-endian  (0) 2011.03.22
지식 기반 문제  (0) 2011.03.21
bit operations 총 정리  (0) 2011.01.09
Saturation arithmetic  (0) 2009.12.17
AND & XOR  (0) 2009.12.15

Frank kenshin579 programming/programming interview saturation arithmetic

AND & XOR

2009.12.15 16:36
AND (Selection?)
A AND B ==> always selects the lower number
Ex.
0001(1) & 0011(3) => 0001(1)
0010(2) & 0011(3) => 0010(2)
 
XOR (Addition)
A XOR B ==> always combine both numbers
Ex.
0001(1) ^ 0011(3) => 0011(3)
0010(2) ^ 0100(4) => 0110(6)

Usage:
int zi = 0;
xor %eax, %eax # zi = 0



저작자 표시
신고

'programming > programming interview' 카테고리의 다른 글

Counting ones  (0) 2011.03.23
big-endian and little-endian  (0) 2011.03.22
지식 기반 문제  (0) 2011.03.21
bit operations 총 정리  (0) 2011.01.09
Saturation arithmetic  (0) 2009.12.17
AND & XOR  (0) 2009.12.15

Frank kenshin579 programming/programming interview And, xor