최근에 프로젝트를 정리하기 시작했고 유용한 코드 비트의 개인 저장소를 만들기로 결정했습니다. 나는 그들 사이에이 비트 맵 코드를 발견하고 그것을 심하게 편집했고 누군가 그것을 검토 할 수 있다면 감사 할 것이다. 왜냐하면 나는 비트 연산 등에 익숙하지 않기 때문이다. 코드를 충분히 이식 할 수 있습니까? 아니면 변경해야합니까?
bitmap.h
#ifndef BITMAP__ #define BITMAP__ #define BIT (8*sizeof(byte)) #define BITMAP_NOTFOUND -1 typedef enum{false=0, true} bool; typedef unsigned char byte; bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); #endif bitmap.c
#include "bitmap.h" static bool get (byte, byte); static void set (byte *, byte); static void reset(byte *, byte); /* CAREFUL WITH pos AND BITMAP SIZE! */ bool bitmapGet(byte *bitmap, int pos) { /* gets the value of the bit at pos */ return get(bitmap[pos/BIT], pos%BIT); } void bitmapSet(byte *bitmap, int pos) { /* sets bit at pos to 1 */ set(&bitmap[pos/BIT], pos%BIT); } void bitmapReset(byte *bitmap, int pos) { /* sets bit at pos to 0 */ reset(&bitmap[pos/BIT], pos%BIT); } int bitmapSearch(byte *bitmap, bool n, int size, int start) { /* Finds the first n value in bitmap after start */ /* size is the Bitmap size in bytes */ int i; /* size is now the Bitmap size in bits */ for(i = start+1, size *= BIT; i < size; i++) if(bitmapGet(bitmap,i) == n) return i; return BITMAP_NOTFOUND; } static bool get(byte a, byte pos) { /* pos is something from 0 to 7*/ return (a >> pos) & 1; } static void set(byte *a, byte pos) { /* pos is something from 0 to 7*/ /* sets bit to 1 */ *a |= 1 << pos; } static void reset(byte *a, byte pos) { /* pos is something from 0 to 7*/ /* sets bit to 0 */ *a &= ~(1 << pos); } 댓글
- 아직이 게시물을 팔로우하는 모든 사람에게 코드를 github 여기 에 커밋했습니다. 또한 귀하의 모든 의견을 이슈로 추가했습니다. 의견을 보내 주셔서 감사합니다. 구현을 시작하겠습니다.
답변
귀하의 코드가 C ++ (많은 C 코드)에서 사용 된 경우 이중 밑줄이있는 식별자를 사용해서는 안됩니다.
#ifndef BITMAP__ // ^^ May cause problems in C++ 이것은 구현을 위해 예약되어 있습니다. C ++에서. 또한 BITMAP라는 용어는 매우 일반적이며 다른 라이브러리와 충돌 할 가능성이 매우 높으며 프로젝트에 더 고유하게 만들려고합니다.
문자는 8 비트라고 가정합니다.
#define BIT (8*sizeof(byte)) 표준은 이것을 말하지 않지만 (최소 8 비트) 실제로 CHAR_BITS 매크로를 통해 정의되므로 다음을 사용해야합니다.
#define BIT (CHAR_BITS*sizeof(byte)) 헤더 파일은 대부분의 사람들이 코드를 먼저보고 코드 사용 방법을 이해하는 방법입니다. 따라서 매개 변수 이름을 헤더 파일에 넣는 것은 사용법을 문서화하는 데 도움이되므로 아마도 좋은 생각 일 것입니다.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); 는 명확하지 않으므로 헤더에서의 사용법에 대한 주석은 아마도 좋은 생각 일 것입니다. 실제로 첫 번째 매개 변수가 배열이 될 수있는 방법에 대한 간단한 설명은 아마도 좋은 생각 일 것입니다 (코드를 읽지 않고는 분명하지 않기 때문입니다).
주석에주의하십시오 :
/* pos is something from 0 to 7*/ 이것은 가정을하는 경우에만 해당됩니다 (A : that sizeof (byte) == 1 B : 여기에 8을 곱합니다). 주석은 다음과 같아야합니다.
/* pos is a value between [0, BIT) */ 왼쪽에는 “[“, 오른쪽에는 “)”이 사용되었습니다. 0이 포함되고 BIT가 범위에 포함되지 않음을 나타내는 수학적 표기법입니다 (C / C ++ 문서 모두에서 일반적 임).
Answer
-
타입은 불필요합니다. 표준 라이브러리처럼 부호없는 char 및 int를 사용하십시오.
-
C에서 0이 아닌 것은 실제 상태를 나타 내기 때문에 동일한 주제에서 열거 형 부울이 필요하지 않습니다. get ()은 값 1이 참이라고 가정하기 때문에 자신을 확인합니다. 모든 사람이 이것을 가정하므로 유형이 중복됩니다. 또한 열거 형을
typedef enum{true=0, false} bool;로 변경하면 논리적으로 합당한 일 임에도 불구하고 함수가 실패하기 때문에 잘못되었습니다.
그런 부울을 사용하려면 값 중 하나를 명시 적으로 반환해야합니다.
return ((a >> pos) & 1) ? true : false;하지만 실제로는 의미가 없습니다. 표준 라이브러리처럼 int를 반환하십시오.
-
bitmapGet ()이 bool을 반환하는 것은 나에게 잘못된 이름으로 보입니다. 비트 맵 비트는 true와 false가 아닌 1과 0의 값을 갖습니다 ( 현재 동일하더라도). 그것을 bitmapIsSet ()라고 부르는 것이 더 논리적 일 것입니다.
-
sizeof (char)는 정의상 1이므로 BIT는 CHAR_BIT로 대체 될 수 있습니다.
-
함수에 대한 여는 괄호는 일반적으로 열 0에 있습니다.
-
bitmapSearch의 매개 변수 순서는 참조하는 항목 (비트 맵)을 따르는 크기가 더 논리적입니다.
-
bitmapSearch의 시작 매개 변수가 잘못되었습니다. 비트 0 (확실히 가장 일반적인)에서 시작하는 검색을 지정하려면 호출자가 -1을 전달해야합니다 !!
-
“pos”매개 변수를 “byte”로 전달하는 이유는 무엇입니까? 비트 맵 바이트를 나타 내기 위해 “byte”를 정의했으며 “pos”는 확실히 그 중 하나가 아닙니다. 프로토 타입으로 인해 너비가 다른 인수를 전달하는 것에 대해 활성화 된 경우 컴파일러 경고가 표시됩니다. 그리고 “pos”를 바이트로 제한하면 추가 기계 명령어 (어셈블러를보십시오)를 추가 할 수 있지만 아무것도 달성하지 못할 수 있습니다. 원하는 것으로 보이는 범위가 0..7 인 pos_t 유형을 정의 할 수 있다면 그것이 어떤 식 으로든 정확하다고 주장 할 수 있지만 C에서는 그렇게 할 수없고 분명히 바이트 값의 범위가 0입니다. 255, 정수를 사용하는 것보다 낫지 않습니다.
답변
하지 않았습니다. 성능에 대해 물어 보지만, 한 번에 한 바이트 씩 먼저 살펴봄으로써 희소 비트 맵의 bitmapSearch 속도를 높일 수 있습니다. 1을 찾는 경우 0x00 인 바이트를 건너 뛸 수 있습니다. 0을 찾으면 0xFF 인 바이트를 건너 뛸 수 있으며 그 후에 다음 바이트의 비트를 스캔하거나 그에 대한 조회 테이블을 사용할 수 있습니다.
API에 관한 한
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); 를 추가 할 수 있으므로 클라이언트는 할당.
그리고 / 또는 할당에 도움이되는 매크로를 제공합니다. 배열 할당에 나타나게하려면 함수 대신 매크로를 사용하세요.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) 또한 bitmapSearch는 바이트 수 대신 비트 수로 크기를 가져옵니다. 그런 다음 클라이언트가 문자에 대해 26 비트 만 신경 쓰는 경우 “비트 맵에 실제로 32 비트가 포함되어 있으므로 27을 반환하는 검색에 대해 걱정할 필요가 없습니다.