Форум программистов, компьютерный форум CyberForum.ru

Нумерация битов в битовых полях - C++

Восстановить пароль Регистрация
 
 
anwender95
0 / 0 / 0
Регистрация: 31.03.2014
Сообщений: 10
31.03.2014, 16:19     Нумерация битов в битовых полях #1
Здравствуйте!
У меня есть битовое поле и юнион:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct bitfield{
    bool b0:1;
    bool b1:1;
    bool b2:1;
    bool b3:1;
    bool b4:1;
    bool b5:1;
    bool b6:1;
    bool b7:1;
    bool b8:1;
    bool b9:1;
    bool b10:1;
    bool b11:1;
    bool b12:1;
    bool b13:1;
    bool b14:1;
    bool b15:1;
};
union byte{
    bitfield p; //part
    short int a; //all
};
Меня интересует, можно ли обращаться к номерам битов через переменную?
Типа
C++
1
2
3
for(int i=0;i<15;i++){
word2.p.bi;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.04.2014, 22:00     Нумерация битов в битовых полях
Еще ссылки по теме:

Выполнение битовых логических операций C++
Реализация битовых операций в Си++ C++
C++ Уточнение о полях структуры

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

Или воспользуйтесь поиском по форуму:
DrOffset
6426 / 3800 / 880
Регистрация: 30.01.2014
Сообщений: 6,594
01.04.2014, 22:00     Нумерация битов в битовых полях #21
Цитата Сообщение от SatanaXIII Посмотреть сообщение
смысл был в том, чтобы создать удобный интерфейс работы с битовым полем по его номеру, без использования сдвигов
В общем случае ты от сдвигов все равно никуда не уйдешь Биты-то нельзя адресовать, сам же написал. Хотя, что-то мне подсазывает (приду домой - сделаю тест), что современный компилятор сделает примерно эквивалентный код при доступе через битовые поля или сдвиги.

Добавлено через 5 часов 15 минут
SatanaXIII, Итак. Я сделал два базовых теста. Один простой с inplace заданием битов.
Первый тест
Кликните здесь для просмотра всего текста
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
#include <cstdio>
 
struct word_bits
{
    bool b0  : 1;
    bool b1  : 1;
    bool b2  : 1;
    bool b3  : 1;
    bool b4  : 1;
    bool b5  : 1;
    bool b6  : 1;
    bool b7  : 1;
    bool b8  : 1;
    bool b9  : 1;
    bool b10 : 1;
    bool b11 : 1;
    bool b12 : 1;
    bool b13 : 1;
    bool b14 : 1;
    bool b15 : 1;
};
 
union word_union
{
    word_bits data;
    short int raw;
};
 
short int test1()
{
    word_union value = word_union();
 
    value.data.b3 = 0;
    value.data.b2 = 1;
    value.data.b1 = 1;
    value.data.b0 = 0;
 
    return value.raw;
}
 
short int test2()
{
    short value = 0;
 
    value &= ~(1 << 3);
    value |=  (1 << 2);
    value |=  (1 << 1);
    value &= ~(1 << 0);
 
    return value;
}
 
int main()
{
    short int v1 = test1();
    printf("%d\n", v1);
 
    short int v2 = test2();
    printf("%d\n", v2);
}

Как видно, примеры абсолютно эквивалентны. Компилятор, как и ожидается, заменил это на банальнейший код:
Кликните здесь для просмотра всего текста
Assembler
1
2
3
4
5
6
test1:
    mov eax, 6
    ret
test2:
    mov eax, 6
    ret

Собственно в этом не было сомнений. Теперь давай проэмулируем ситуацию, когда значения битов не известны заранее, чтобы заблокировать эту оптимизацию.
Второй пример:
Кликните здесь для просмотра всего текста
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
#include <cstdio>
 
struct word_bits
{
    bool b0  : 1;
    bool b1  : 1;
    bool b2  : 1;
    bool b3  : 1;
    bool b4  : 1;
    bool b5  : 1;
    bool b6  : 1;
    bool b7  : 1;
    bool b8  : 1;
    bool b9  : 1;
    bool b10 : 1;
    bool b11 : 1;
    bool b12 : 1;
    bool b13 : 1;
    bool b14 : 1;
    bool b15 : 1;
};
 
union word_union
{
    word_bits data;
    short int raw;
};
 
extern bool a0 = 0;
extern bool a1 = 1;
extern bool a2 = 0;
extern bool a3 = 0;
 
short int test1()
{
    word_union value = word_union();
 
    value.data.b3 = a3;
    value.data.b2 = a2;
    value.data.b1 = a1;
    value.data.b0 = a0;
 
    return value.raw;
}
 
short int test2()
{
    short value = 0;
 
    a3 ? value |= (1 << 3) : value &= ~(1 << 3);
    a2 ? value |= (1 << 2) : value &= ~(1 << 2);
    a1 ? value |= (1 << 1) : value &= ~(1 << 1);
    a0 ? value |= (1 << 0) : value &= ~(1 << 0);
 
    return value;
}
 
int main()
{
    short int v1 = test1();
    printf("%d\n", v1);
 
    short int v2 = test2();
    printf("%d\n", v2);
}

Хехе, похоже ситуация здесь не в пользу второго варианта. Ну это должно быть понятно даже без асма, ведь очевидно, что здесь компилятору придется делать сравнения:
Кликните здесь для просмотра всего текста
Assembler
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
test1:
    push    ebx
    movzx   eax, BYTE PTR _a3
    and eax, 1
    sal eax, 3
    movzx   edx, BYTE PTR _a2
    and edx, 1
    lea ebx, [0+edx*4]
    movzx   edx, BYTE PTR _a1
    and edx, 1
    lea ecx, [edx+edx]
    or  eax, ebx
    movzx   edx, BYTE PTR _a0
    and edx, 1
    or  eax, ecx
    or  eax, edx
    pop ebx
    ret
test2:
    xor eax, eax
    cmp BYTE PTR _a3, 0
    setne   al
    sal eax, 3
    cmp BYTE PTR _a2, 0
    je  L5
    or  eax, 4
    cmp BYTE PTR _a1, 0
    je  L7
L14:
    or  eax, 2
    cmp BYTE PTR _a0, 0
    jne L13
L9:
    and eax, -2
    ret
L5:
    and eax, -5
    cmp BYTE PTR _a1, 0
    jne L14
L7:
    and eax, -3
    cmp BYTE PTR _a0, 0
    je  L9
L13:
    or  eax, 1
    ret

Однако и с битовыми полями не все так приятно. Как я и говорил, бесплатно это не дается, хоть это и лучше чем второй вариант. Кстати обратите внимание, сдвиг (но только один!) есть в обоих вариантах. Но проблема второго именно в сравнениях и прыжках, а не в сдвигах. Можно избавиться от прыжков, если использовать вычисление обоих значений на каждом этапе в таблицу, а булевый флаг использовать в качестве индекса.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void setBit(short & value, size_t idx, bool bit)
{
    const short int values[] = { value & ~(1 << idx), value | (1 << idx) };
    value = values[bit];
}
 
short int test2()
{
    short value = 0;
 
    setBit(value, 3, a3);
    setBit(value, 2, a2);
    setBit(value, 1, a1);
    setBit(value, 0, a0);
 
    return value;
}

Кликните здесь для просмотра всего текста
Assembler
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
test2:
    sub esp, 16
    mov WORD PTR [esp+12], 0
    mov WORD PTR [esp+14], 8
    movzx   eax, BYTE PTR _a3
    mov ax, WORD PTR [esp+12+eax*2]
    mov edx, eax
    and edx, -5
    mov WORD PTR [esp+12], dx
    or  eax, 4
    mov WORD PTR [esp+14], ax
    movzx   eax, BYTE PTR _a2
    mov ax, WORD PTR [esp+12+eax*2]
    mov edx, eax
    and edx, -3
    mov WORD PTR [esp+12], dx
    or  eax, 2
    mov WORD PTR [esp+14], ax
    movzx   eax, BYTE PTR _a1
    mov ax, WORD PTR [esp+12+eax*2]
    mov edx, eax
    and edx, -2
    mov WORD PTR [esp+12], dx
    or  eax, 1
    mov WORD PTR [esp+14], ax
    movzx   eax, BYTE PTR _a0
    mov ax, WORD PTR [esp+12+eax*2]
    add esp, 16
    ret

Похоже этот вариант отлично ляжет в кеш процессора. Хотя вариант в битовыми полями все еще лучше.
Но это еще не все. Весь-то сыр-бор затевался из-за индексированного доступа. Только ой. Во втором варианте он уже есть. Так сказать из коробки. Для правильной оценки я переписал пример так (эмулируем ситуацию с массивом с неизвестным содержанием, который надо представить в виде нашего битсета):
Кликните здесь для просмотра всего текста
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <cstdio>
 
struct word_bits
{
    bool b0  : 1;
    bool b1  : 1;
    bool b2  : 1;
    bool b3  : 1;
    bool b4  : 1;
    bool b5  : 1;
    bool b6  : 1;
    bool b7  : 1;
    bool b8  : 1;
    bool b9  : 1;
    bool b10 : 1;
    bool b11 : 1;
    bool b12 : 1;
    bool b13 : 1;
    bool b14 : 1;
    bool b15 : 1;
};
 
union word_union
{
    word_bits data;
    short int raw;
};
 
inline void setBit(word_union & value, size_t idx, bool bit)
{
    switch(idx)
    {
    case 0:
        value.data.b0 = bit;
        break;
    case 1:
        value.data.b1 = bit;
        break;
    case 2:
        value.data.b2 = bit;
        break;
    case 3:
        value.data.b3 = bit;
        break;
    case 4:
        value.data.b4 = bit;
        break;
    case 5:
        value.data.b5 = bit;
        break;
    case 6:
        value.data.b6 = bit;
        break;
    case 7:
        value.data.b7 = bit;
        break;
    case 8:
        value.data.b8 = bit;
        break;
    case 9:
        value.data.b9 = bit;
        break;
    case 10:
        value.data.b10 = bit;
        break;
    case 11:
        value.data.b11 = bit;
        break;
    case 12:
        value.data.b12 = bit;
        break;
    case 13:
        value.data.b13 = bit;
        break;
    case 14:
        value.data.b14 = bit;
        break;
    case 15:
        value.data.b15 = bit;
        break;
    }
}
 
extern bool values[] = { 1, 0, 1, 1 };
 
short int test1()
{
    word_union value = word_union();
 
    for(size_t i = 0; i < sizeof(values)/sizeof(*values); ++i)
    {
        setBit(value, i, values[i]);
    }
    return value.raw;
}
 
 
inline void setBit(short & value, size_t idx, bool bit)
{
    const short values[] = { short(value & ~(1 << idx)), short(value | (1 << idx)) };
    value = values[bit];
}
 
short int test2()
{
    short int value = 0;
 
    for(size_t i = 0; i < sizeof(values)/sizeof(*values); ++i)
    {
        setBit(value, i, values[i]);
    }
    return value;
}
 
int main()
{
    short int v1 = test1();
    printf("%d\n", v1);
 
    short int v2 = test2();
    printf("%d\n", v2);
}

А здесь вот что, специально не стану убирать это под спойлер:
Assembler
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
test1:
    push    edi
    push    esi
    push    ebx
    xor eax, eax
    xor esi, esi
    xor edi, edi
    mov edx, 1
    mov bl, BYTE PTR _values[edx-1]
    lea ecx, [edx-1]
    cmp ecx, 2
    je  L5
L17:
    cmp ecx, 3
    je  L6
    dec ecx
    je  L4
    cmp edx, 4
    je  L16
    mov al, bl
    inc edx
L18:
    mov bl, BYTE PTR _values[edx-1]
    lea ecx, [edx-1]
    cmp ecx, 2
    jne L17
L5:
    mov edi, ebx
    mov ebx, esi
L4:
    mov esi, ebx
    inc edx
    jmp L18
 
L6:
    and eax, 1
    and esi, 1
    sal esi
    and edi, 1
    sal edi, 2
    or  eax, esi
    and ebx, 1
    sal ebx, 3
    or  eax, edi
    or  eax, ebx
L13:
    pop ebx
    pop esi
    pop edi
    ret
L16:
    mov eax, ebx
    and eax, 1
    mov ecx, esi
    and ecx, 1
    sal ecx
    mov edx, edi
    and edx, 1
    sal edx, 2
    or  eax, ecx
    or  eax, edx
    jmp L13
Однако, правда? Собственно к этому я и вел, когда запостил свой наколеночный вариант. Битовые поля и индексация вещь плохо совместимая. Хотя компилятор очень хорошо оптимизировал этот вариант, сведя к минимуму количество сравнений.
А вот второй вариант, видно что для индексации он гораздо лучше подходит:
Assembler
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
test2:
    push    esi
    push    ebx
    sub esp, 16
    xor eax, eax
    xor ecx, ecx
    mov esi, 1
L20:
    mov ebx, esi
    sal ebx, cl
    mov edx, ebx
    not edx
    and edx, eax
    mov WORD PTR [esp+12], dx
    or  eax, ebx
    mov WORD PTR [esp+14], ax
    movzx eax, BYTE PTR _values[ecx]
    mov ax, WORD PTR [esp+12+eax*2]
    inc ecx
    cmp ecx, 4
    jne L20
    add esp, 16
    pop ebx
    pop esi
    ret
Ну и как резюме:я ни в коем случае не отрицаю эффективность битовых полей. С ними у компилятора гораздо больше возможностей сделать оптимизацию. Но индексация на базе них как собаке пятая нога. А из-за switch можно забыть про возможность красиво обобщить решение.

PS. Опубликовано тут исключительно в образовательных целях
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Yandex
Объявления
01.04.2014, 22:00     Нумерация битов в битовых полях
Ответ Создать тему
Опции темы

Текущее время: 15:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru