가능한 경우 C에서 2 비트 숫자를 정의하는 방법은 무엇입니까?

Question

제 대학 과정에서 무작위 순차 흡착이라는 과정을 시뮬레이션하고 있습니다. 내가해야하는 일 중 하나는 무작위로 격자에 겹치지 않는 사각형을 무작위로 쌓아 놓고 더 이상 공간이 남아 있지 않을 때까지 평균 '방해 전파'범위를 찾는 과정을 여러 번 반복하는 것입니다.

기본적으로 나는 3 개의 가능한 값인 0, 1 및 2가있는 큰 정수 배열에 연산을 수행하고 있습니다. '0'으로 표시된 사이트는 비어 있으며 '1'로 표시된 사이트는 꽉 찼습니다. 처음 배열은 다음과 같이 정의된다 :

int i, j; 
int n = 1000000000; 
int array[n][n]; 

for(j = 0; j < n; j++) 
{ 
    for(i = 0; i < n; i++) 
    { 
     array[i][j] = 0; 
    } 
} 

내가 사각형이 '1의로 표현되도록 (즉 겹칠 수 없습니다) 배열에 무작위로 5 개 * 5 사각형을 입금하고 싶은 말은. 이것은 무작위로 x와 y 좌표를 선택한 다음 그 점에서 시작하는 사각형의 topleft 점으로 '5'* 5 제곱을 만드는 것입니다. 그러면 광장 근처에있는 사이트를 '2'라고 표시합니다. 이들은 해당 사이트에서 정사각형을 입금하면 기존 정사각형과 겹칠 수 있기 때문에 사용할 수없는 사이트를 나타냅니다. 이 과정은 어레이에 정사각형을 놓을 여지가 없어 질 때까지 계속됩니다 (기본적으로 어레이에 0이 더 이상 남아 있지 않습니다).

어쨌든, 요점은. 비트 연산을 사용하여 가능한 한 효율적으로이 프로세스를 만들고 싶습니다. 내가 사각형 근처에 사이트를 표시 할 필요가 없다면 이것은 쉽습니다. 나는 '2'로 표시된 사이트를 설명 할 수 있도록 2 비트 숫자를 생성 할 수 있는지 궁금합니다.

죄송합니다. 정말 복잡한 것처럼 들리면, 왜 내가 이것을하고 싶은지 설명하고 싶었습니다.

Answer 1

2 비트 어레이 대신 2 개의 별도의 1 비트 어레이를 사용할 수 있습니다. 하나는 채워진 사각형을 보유하고 하나는 인접한 사각형 (또는 이것이 더 효율적인 경우 사용 가능한 사각형)을 보유합니다.

2 비트 필드를 단어로 채우는 것보다 이것이 어떤 이점이 있는지 잘 모르겠습니다. 메모리가 부족하지 않으면 바이트 배열로 이동합니다.

Answer 2

주소 지정이 불가능하므로 2 비트 크기의 데이터 유형을 만들 수 없습니다.

struct Cell { 
     a : 2; 
     b : 2; 
     c : 2; 
     d : 2; 
    }; 

이 회원 a, b, c 및 d의 각 메모리에 두 개의 비트를 차지하도록 지정합니다 : 당신이 할 수있는 것은 더 큰 셀에 여러 개의 2 비트 숫자를 팩입니다.

편집 :이 가장 효율적인 구현이 아마 int의 배열을 생성하고 몇 바이올린을 켜는 비트를 마무리하는 것입니다 문제의 실제 문제에 대한, 2 비트의 변수를 만드는 방법에 단지 예입니다 set/get 개의 방법이있다.

Answer 3

배열의 한 차원을 하위 정수 셀로 압축 할 수 있습니다.

byte cell = array[i][ x/4 ]; 
byte mask = 0x0004 << (x % 4); 
byte data = (cell & mask) >> (x % 4); 

데이터가

Answer 4

역의 기본 개념 불행하게도

않습니다 쓰기,이 작업을 수행 할 수있는 방법이 없습니다 : 좌표 변환하려면 내부 바이트의 위치를 ​​(예를 들어 X를 말할 수) C. 1 바이트, 2 바이트 등의 배열을 만들 수 있습니다.하지만 비트 영역을 만들 수는 없습니다.

당신이 할 수있는 가장 좋은 방법은 자신을 위해 새로운 라이브러리를 작성하는 것입니다. 그러면 2 비트 배열을 처리하는 것처럼 보이지만 사실 실제로 많은 노력이 필요합니다. 문자열 라이브러리가 "문자열"(C는 그냥 배열)에서 작동하는 함수를 제공하는 것과 같은 방식으로 "비트 배열"에서 작동하는 새 라이브러리를 생성하게됩니다 (실제로는 정수 배열입니다. 비트 단위의 배열 인 경우이를 다루는 몇 가지 특수 함수가 있음).

참고 : C를 처음 접했을 때 "새로운 라이브러리/모듈 만들기"아이디어 나 "추상화"개념을 배우지 못했다면 계속하기 전에 배우는 것이 좋습니다. 이 프로젝트에 IMO는 프로그램을 최적화하여 공간을 조금 절약하는 것보다 중요합니다.

사용자의 요구를 들어이 새로운 "라이브러리"또는 모듈

을 구현하는 방법, 나는 2 비트의 배열을 처리하는 함수를 내 보냅니다 "2 비트 배열"라는 새로운 모듈을 만들 것 , 필요에 따라

설정 비트/읽기 비트를 처리하는 몇 가지 기능이 있으므로 실제 비트 배열을 가진 것처럼 작업 할 수 있습니다 (실제로 정수 배열이나 배열이 있지만 모듈 당신에게 비트 배열이있는 것처럼 보일 것입니다.)

이런 일을하고자이 모듈을 사용 :

할 실제로 것입니다 모듈이 정수의 정기적 된 배열을 사용하여 모든 기능을 구현 무엇

// This is just an example of how to use the functions in the twoBitArray library. 
twoB my_array = Create2BitArray(size); // This will "create" a twoBitArray and return it. 
SetBit(twoB, 5, 1); // Set bit 5 to 1 // 
bit b = GetBit(twoB, 5); // Where bit is typedefed to an int by your module. 

. 예를 들어

, 기능 GetBit(), GetBit(my_arr, 17), 그것은 당신의 배열 (분명히, sizeof(int)에 따라 다름)의 4 정수의 1 비트 있다는 계산합니다, 당신은 비트 연산을 사용하여 반환 것입니다.