Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
#1

Как лучше сделать. - C++

03.09.2009, 10:04. Просмотров 931. Ответов 16
Метки нет (Все метки)

В общем сейчас есть такая задача.
Есть спрайт (допустим 800х600)
мне нужно что бы под каждую "точку" выделялся один бит.
при этом что бы я мог обратися к каждому биту, имея его порядковый номер
Как это лучше сделать. Спасибо.
все что пока приходит в голову:
C++
1
2
3
4
5
6
7
8
char* I=new [60000];
 
bool getbit(int x,int y){
int p=(y<<9+y<<8+y<<5+x);
int n=p&7;//тут получаем номер интересуещего нас бита
p>>3;//тут смещение по которому находится интересующий нас байт
return (I[p]&1<<n)>>n;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.09.2009, 10:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как лучше сделать. (C++):

Посоветуйте, как лучше сделать - C++
Для шифрования текста выбираем n и перестановку чисел от 1 до n. Текст разбиваем на группы по n и в каждой группе переставляем символы в...

Как лучше это сделать?. а главное, как правильно? (Информационная система «Железнодорожный вокзал») - C++
Ситуация следующая... Есть задание курсовой работы: 11. Информационная система «Железнодорожный вокзал». Информация: рейсы — номер...

Как лучше сделать иерархию классов? - C++
Здравствуйте! Мой вопрос заключается в том, что я хочу понять как лучше сделать иерархию классов: шаблонами или простым множественных...

Как лучше сделать глобальную переменную? - C++
Интернет совсем пустой в плане глобальных переменных на с++ Задача следующая: 1. Нужно создать много глобальных переменных будет...

Печать квадрата из звездочек. Как сделать лучше? - C++
Я написал программу, которая печатает из звездочек квадрат с заданной стороной. Например, квадрат со стороной 6 будет выглядеть так: ...

Найти 2-ю цифру из числа. Как сделать лучше? - C++
Имеется прога #include &lt;iostream&gt; #include &lt;fstream&gt; using namespace std; int main() { int x;

16
АНК
124 / 115 / 2
Регистрация: 27.02.2007
Сообщений: 291
03.09.2009, 10:51 #2
Я предложил бы такое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool getbit(unsigned char * ar, int x, int y);
void __fastcall TTestForm::Button1Click(TObject *Sender)
{
  unsigned char* I = new unsigned char [60000]; // т.е. 600 строк по 100 байтов
  bool btn = getbit(I, 333, 444);
}
 
bool getbit(unsigned char * ar, int x, int y)
{
  int i_byte = x/8; // какой байт в строке
  int i_pos = x%8;  // позиция точки в байте
  // маска выделения нужного бита
  unsigned char msk = 1;
  if(i_pos != 0) msk <<= i_pos;
 
  int index = y*100 + i_byte; // адрес байта в массиве
  return (ar[index] & msk) != 0;
}
Ну, конечно, надо бы вставить проверку для x и y на не превышение размера.
1
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
03.09.2009, 11:19  [ТС] #3
Спасибо, но тут основной критерий в быстродействии, т.к. работа происходит с динамически меняющимся изображением. процесс заполнения должен происходить на фоне емких (в процессорном времени) операций, многие из которых реализованы на ассемблере.
0
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
03.09.2009, 17:02  [ТС] #4
Возник такой вопрос: оператор ! побитный или как? и есть ли побитное НЕ?
0
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
03.09.2009, 17:24 #5
если скорость - решающий фактор:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define BYTES_IN_ROW 100
#define BITS_IN_BYTE 8
 
char* pBitmatrix=new char [60000];
 
bool isBit (int x,int y){
    char mask = 0;
    switch (x%8){
        case 0:
            mask = '\x80';
            break;
        case 1:
            mask = '\x40';
            break;
        case 2:
            mask = '\x20';
            break;
        case 3:
            mask = '\x10';
            break;
        case 4:
            mask = '\x08';
            break;
        case 5:
            mask = '\x04';
            break;
        case 6:
            mask = '\x02';
            break;
        case 7:
            mask = '\x01';
            break;
    }
    return *(pBitmatrix + BYTES_IN_ROW*y + x/BITS_IN_BYTE) | mask != '\x00';
}
что-то я в последней строчке нахомутал, но думать и исправлять - лень может, не x/BITS_IN_BYTE, а x%BITS_IN_BYTE ? без понятия! в отпуске я
0
Yurii_74
paladin
280 / 180 / 3
Регистрация: 25.02.2009
Сообщений: 592
03.09.2009, 17:26 #6
Цитата Сообщение от Mozart Посмотреть сообщение
Возник такой вопрос: оператор ! побитный или как? и есть ли побитное НЕ?
побитное НЕ может реализовываться через исключающее или с 0xff (для unsigned char).

! - вроде как логический. иначе для
int t=2;
!t не было бы нулем.
1
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
03.09.2009, 18:02  [ТС] #7
Все, вспомнил про такую чудную операцию, спасибо.
novi4ok, Когда речь идет о скорости, я стараюсь избегать какие либо деления умножения и прочие условия. Потому теперешний код имеет слудующий вид:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdlib>
#include <iostream>
char* I=new char [60000];
 
bool getbit(int x,int y){
     int p=((y<<9)+(y<<8)+(y<<5)+x);
     int n=p&7;//тут получаем номер интересуещего нас бита
     p>>=3;//тут смещение по которому находится интересующий нас байт
     return (I[p]&(1<<n))>>n;
}
void setbit(int x,int y){
     int p=((y<<9)+(y<<8)+(y<<5)+x);
     int n=p&7;//тут получаем номер интересуещего нас бита
     p>>=3;//тут смещение по которому находится интересующий нас байт
     char mask=(1<<n);
     I[p]|=mask;
}
void clearbit(int x,int y){
     int p=((y<<9)+(y<<8)+(y<<5)+x);
     int n=p&7;//тут получаем номер интересуещего нас бита
     p>>=3;//тут смещение по которому находится интересующий нас байт
     char mask=(1<<n)^0xFF;
     I[p]&=mask;
}
using namespace std;
 
int main(int argc, char *argv[])
{
    setbit(5,599);
    setbit(3,599);
    setbit(7,599);
    setbit(2,599);
    clearbit(3,599);
    for (int j=598;j<600;j++){
        cout<<j<<":"<<endl;
        for (int i=0;i<800;i++)cout<<getbit(i,j);
}
 
int y=599,x=799;
cout<<(((y<<9)+(y<<8)+(y<<5)+x)>>3)<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
delete[] I;
}
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
03.09.2009, 18:52 #8
Если так важно быстролействие, то эти функции должны быть inline. Насчёт кучи битовых сдвигов мне что-то кажется, что одно умножение будет лучше, чем три сдвига и два лишних сложения.
И (I[p]&(1<<n))>>n ---> (I[p] >> n) & 1.
1
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
03.09.2009, 19:16 #9
Mozart, я хоть и в отпуске, но не поленился померять. мой код и понятней (т.е. менее подвержен ошибкам и изначально, и тем более при сопровождении), и (вы не поверите!) выполняется быстрее.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#define BYTES_IN_ROW 100
#define BITS_IN_BYTE 8
 
char* pBitmatrix=new char [60000];
 
bool isBit (int x,int y){
    char mask = 0;
    switch (x%8){
        case 0:
            mask = '\x80';
            break;
        case 1:
            mask = '\x40';
            break;
        case 2:
            mask = '\x20';
            break;
        case 3:
            mask = '\x10';
            break;
        case 4:
            mask = '\x08';
            break;
        case 5:
            mask = '\x04';
            break;
        case 6:
            mask = '\x02';
            break;
        case 7:
            mask = '\x01';
            break;
    }
    return (*(pBitmatrix + BYTES_IN_ROW*y + x/BITS_IN_BYTE) | mask) != '\x00';
}
 
bool getbit(int x,int y){
     int p=((y<<9)+(y<<8)+(y<<5)+x);
     int n=p&7;
     p>>=3;
     return (pBitmatrix[p]&(1<<n))>>n;
}
 
unsigned __int64 inline GetRDTSC() {
   __asm {
      ; Flush the pipeline
      XOR eax, eax
      CPUID
      ; Get RDTSC counter in edx:eax
      RDTSC
   }
}
 
/////////////////////////
//
int main() {
 
    bool b;
    unsigned int i;
 
    unsigned __int64 a1 = GetRDTSC();
 
 
    for (i = 0; i < 10000000; i++){
        b = isBit (2, 20);
    }
 
    unsigned __int64 a2 = GetRDTSC();
 
    for (i = 0; i < 10000000; i++){
        b = getbit (2,20);
    }
    
    unsigned __int64 a3 = GetRDTSC();
    
    unsigned __int64 diffNovi4ok = a2-a1;
    unsigned __int64 diffMozart = a3-a2;
 
    bool isMozartFaster = diffMozart < diffNovi4ok;
Добавлено через 23 минуты
да, нахомутал я совсем не то что думал. правильно так:

C++
1
return (*(pBitmatrix + BYTES_IN_ROW*y + x/BITS_IN_BYTE) & mask) != '\x00';
кстати, ваш код еще и работает неправильно:

C++
1
2
3
4
5
6
7
8
9
10
11
12
    ::memset (pBitmatrix, 0, 60000);
    *(pBitmatrix+102) = '\x02';// что должно установить бит с x,y = {22,1} 
 
       //будет работать правильно после исправления указанной ошибки
    bool b = isBit (22, 1);
    b = isBit (21, 1);
    b = isBit (23, 1);
 
       //будет возвращать во всех случаях false
    b = getbit (22, 1);
    b = getbit (21, 1);
    b = getbit (23, 1);
0
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
03.09.2009, 19:35  [ТС] #10
Цитата Сообщение от Somebody Посмотреть сообщение
Насчёт кучи битовых сдвигов мне что-то кажется, что одно умножение будет лучше, чем три сдвига и два лишних сложения.
Не соглашусь, т.к.
Умножение (MUL) и Умножение с накоплением (MLA) с 32-битным результатом
Обе команды для выполнения целочисленного умножения используют алгоритм, основанный на цепочке операций логического сдвига и сложения 8-битных операндов (Booth's algorithm).
Добавлено через 7 минут
Цитата Сообщение от novi4ok Посмотреть сообщение
кстати, ваш код еще и работает неправильно:
Странно, у меня работает и ставит куда надо, и возвращает что поставил Х_Х
0
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
03.09.2009, 19:40 #11
Цитата Сообщение от Mozart Посмотреть сообщение
Не соглашусь, т.к.
а вы замеряйте, ведь не сложно. зачем догадки, если вот оно - в реальности.

Цитата Сообщение от Mozart Посмотреть сообщение
Странно, у меня работает и ставит куда надо, и возвращает что поставил Х_Х
вы ставите вашей ф-ей, и опрашиваете вашей ф-ей, обе из них могут содержать ту же ошибку. сейчас проверю, куда ваш set битик запишет.
0
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
03.09.2009, 19:46  [ТС] #12
Я бы с радостью померял, но:
Цитата Сообщение от novi4ok Посмотреть сообщение
unsigned __int64 inline GetRDTSC() {
__asm {
; Flush the pipeline
XOR eax, eax
CPUID
; Get RDTSC counter in edx:eax
RDTSC
}
}
у меня отказывается компилироватся (Dev-C++)
0
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
03.09.2009, 19:49 #13
понял. у вас биты слева направо считаются: самый левый бит в самоа первом байте - это координата не 0,0, а 7,0. но это - не принципиально. в моем варианте только маски поменять в switch'е. она все равно понятнее и быстрее (хотя и незначительно. но не медленнее 100%!). хотя я вполне понимаю желание применить созданное собственными руками. пусть корявое и труднопонимаемое.

Добавлено через 1 минуту
Цитата Сообщение от Mozart Посмотреть сообщение
Я бы с радостью померял, но:

у меня отказывается компилироватся (Dev-C++)
померяйте другими доступными вам средствами. ведь можно и у вас как-то хотя бы миллисекунды опросить?
0
Mozart
39 / 17 / 1
Регистрация: 21.08.2009
Сообщений: 63
03.09.2009, 20:12  [ТС] #14
Померял и у меня получается что мой код работает быстрее =) проверьте у себя:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdlib>
#include <iostream>
#include <windows.h>
 
#define BYTES_IN_ROW 100
#define BITS_IN_BYTE 8
char* I=new char [60000];
 
bool getbit(int x,int y){
     int p=((y<<9)+(y<<8)+(y<<5)+x);
     int n=p&7;//тут получаем номер интересуещего нас бита
     p>>=3;//тут смещение по которому находится интересующий нас байт
     return (I[p]>>n)&1;
}
void setbit(int x,int y){
     int p=((y<<9)+(y<<8)+(y<<5)+x);
     int n=p&7;//тут получаем номер интересуещего нас бита
     p>>=3;//тут смещение по которому находится интересующий нас байт
     char mask=(1<<n);
     I[p]|=mask;
}
void clearbit(int x,int y){
     int p=((y<<9)+(y<<8)+(y<<5)+x);
     int n=p&7;//тут получаем номер интересуещего нас бита
     p>>=3;//тут смещение по которому находится интересующий нас байт
     char mask=(1<<n)^0xFF;
     I[p]&=mask;
}
 
inline bool isBit (int x,int y){
        char mask = 0;
        switch (x%8){
                case 0:
                        mask = '\x80';
                        break;
                case 1:
                        mask = '\x40';
                        break;
                case 2:
                        mask = '\x20';
                        break;
                case 3:
                        mask = '\x10';
                        break;
                case 4:
                        mask = '\x08';
                        break;
                case 5:
                        mask = '\x04';
                        break;
                case 6:
                        mask = '\x02';
                        break;
                case 7:
                        mask = '\x01';
                        break;
        }
        return (*(I + BYTES_IN_ROW*y + x/BITS_IN_BYTE) | mask) != '\x00';
}
 
using namespace std;
 
int main(int argc, char *argv[])
{
    for (int j=0;j<2;j++){
        for (int i=0;i<800;i++)clearbit(i,j);
        }
    setbit(0,0);
    setbit(3,1);
    setbit(7,1);
    setbit(2,1);
    clearbit(3,1);
    for (int j=0;j<2;j++){
        cout<<j<<":"<<endl;
        for (int i=0;i<800;i++)cout<<getbit(i,j);
        }
 
int y=599,x=799;
cout<<(((y<<9)+(y<<8)+(y<<5)+x)>>3)<<endl;
 
unsigned int a1=GetTickCount();
for (int i=0;i<10000000;i++)getbit(2,4);
unsigned int a2=GetTickCount();
for (int i=0;i<10000000;i++)isBit(2,4);
unsigned int a3=GetTickCount();
cout<<a2-a1<<"    "<<a3-a2<<endl;
 
    system("PAUSE");
    return EXIT_SUCCESS;
delete[] I;
}
0
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
03.09.2009, 20:29 #15
Цитата Сообщение от Mozart Посмотреть сообщение
Померял и у меня получается что мой код работает быстрее =) проверьте у себя:
проверил. после выполнения
C++
1
2
3
4
5
6
7
unsigned long aa1=GetTickCount();
for (int i=0;i<10000000;i++)getbit(2,4);
unsigned long aa2=GetTickCount();
for (int i=0;i<10000000;i++)isBit(2,4);
unsigned long aa3=GetTickCount();
unsigned long dd1 =aa2-aa1;
unsigned long dd2= aa3-aa2;
dd1 (время 10000000 обращений к getbit()) равно 391
dd2 (время 10000000 обращений к isBit()) равно 359

видимо, "дома стены помогают"
0
03.09.2009, 20:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2009, 20:29
Привет! Вот еще темы с ответами:

Нарисовал картинку, как дополнить ее, сделать лучше? - C++
облака горы озеро с волной солнце с лучами

break или как сделать лучше код - C++
Вообщем делал задание &quot;НАйти первый и последний нулевой элемент&quot;,так вот ,дан рабочий код,ну есть интересующий вопрос ,яхотел бы...

Как лучше сделать хранение ссылок на экземпляры класса? - C++
есть необходимость зранить все созданные экземпляры класса придумал сдделать это с помощью статического списка - ничего не вышло - ошибка...

Наследование vs Композиция vs Агрегация: что лучше выбрать? Как лучше передавать объекты в функции? - C++
Добрый день!! Дело вот в чём, я хочу создать класс, внутри которого будут созданы объекты других классов (реализованных в некоторой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru