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

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

Войти
Регистрация
Восстановить пароль
 
 
anwender95
0 / 0 / 0
Регистрация: 31.03.2014
Сообщений: 10
#1

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

31.03.2014, 16:19. Просмотров 1054. Ответов 20
Метки нет (Все метки)

Здравствуйте!
У меня есть битовое поле и юнион:
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;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.03.2014, 16:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нумерация битов в битовых полях (C++):

Перевод таблицы битов и времени в последовательность битов arduino - C++
доброго времени суток в приведенной ниже таблице левый столбец - биты, правый - их длительность. известно, что единичный сигнал длится от...

Операции с побитовыми операторами (число 8 битов и число 9 битов) - C++
Доброго времени суток всем ! Прошу ответа на несложный вопрос (...по крайней мере мне так кажется...) Есть функция: ...

Массив битовых полей - C++
Добрый день! Из файла читается массив 4-битовых значений т.е. по два значения в каждом байте. Можно ли описать массив так, чтобы...

Таблица битовых переходов - C++
Доброго времени суток! Появилась необходимость замены битовых комбинаций по заранее сгенерированным правилам. Суть проблемы такова: имеется...

Обработка Битовых последовательностей - C++
Здравствуйте, помогите пожалуйста решить задачку. Тема: Обработка битовых последовательностей. Нужно реализовать алгоритм инвертирования...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
SatanaXIII
Супер-модератор
Эксперт С++
5616 / 2651 / 246
Регистрация: 01.11.2011
Сообщений: 6,529
Завершенные тесты: 1
01.04.2014, 15:54 #16
aLarman, почти хорошо. Осталось только сделать тоже самое, только чтобы оператор возвращал не ссылку, а копию. Битовое поле-то по ссылке нельзя получить. Было бы можно работать с адресами полей, то легче было бы в union массив добавить и всех делов.
0
aLarman
642 / 563 / 89
Регистрация: 13.12.2012
Сообщений: 2,109
01.04.2014, 15:56 #17
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Битовое поле-то по ссылке нельзя получить
я ними не работал почти, не знал такого
0
DrOffset
7134 / 4275 / 963
Регистрация: 30.01.2014
Сообщений: 7,064
01.04.2014, 16:31 #18
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Битовое поле-то по ссылке нельзя получить.
Да это не обязательно. Да и вообще, сдается мне, битовое поле тут нафиг не упало (кому нужны проблемы с union и выравниванием?). Коли уж так хочется итерировать биты, вот накидал на коленке. В ассемблере никакого криминала не обнаружил. Хорошо оптимизируется, вплоть до подстановки константы, в случае если биты задаются 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
61
62
63
64
65
66
67
68
69
70
71
72
73
template <typename T>
class bitfield
{
    class bitfield_proxy
    {
        friend class bitfield;
 
        bitfield_proxy(bitfield & ctrl, size_t idx)
            : ctrl_(ctrl), shifted_(T(1) << idx)
        { }
        bitfield_proxy(bitfield_proxy const & x)
            : ctrl_(x.ctrl_), shifted_(x.shifted_)
        {}
 
        bitfield_proxy & operator=(bitfield_proxy const &);
 
        bitfield & ctrl_;
        const T    shifted_;
 
    public:
        void operator=(bool bit)
        {
             bit ? ctrl_.data_ |= shifted_ : ctrl_.data_ &= ~shifted_;
        }
        operator bool() const
        {
            return ctrl_.data_ & shifted_;
        }
    };
 
    T data_;
 
public:
    bitfield(T data = T())
        : data_(data)
    {}
 
    bool operator[](size_t idx) const
    {
        return data_ & (T(1) << idx);
    }
    bitfield_proxy operator[](size_t idx)
    {
        return bitfield_proxy(*this, idx);
    }
    size_t size() const
    {
        return sizeof(T) / 8; // Вместо 8, кошернее будет CHAR_BITS
    }
    T value() const
    {
        return data_;
    }
};
 
short int test()
{
    bitfield<short int> bits;
 
    bits[3] = 0;
    bits[2] = 1;
    bits[1] = 1;
    bits[0] = 1;
 
    return bits.value();
}
 
int main()
{
    short int v = test();
 
    printf("value: %d\n", v);
}
2
Tulosba
:)
Эксперт С++
4395 / 3238 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
01.04.2014, 16:34 #19
Цитата Сообщение от SatanaXIII Посмотреть сообщение
То, что у бита нет адреса. Не получится перегрузить &operator[].
Всё же это разные вещи, получать доступ на чтение/запись некоторого бита и пытаться (безуспешно) вернуть ссылку или указатель на бит.
Тут, кстати, сразу вспоминается реализация std::vector<bool>, где для минимизации памяти использовали биты для хранения значений.
1
SatanaXIII
Супер-модератор
Эксперт С++
5616 / 2651 / 246
Регистрация: 01.11.2011
Сообщений: 6,529
Завершенные тесты: 1
01.04.2014, 16:36 #20
DrOffset, смысл был в том, чтобы создать удобный интерфейс работы с битовым полем по его номеру, без использования сдвигов. В идеале как по индексу.
1
DrOffset
7134 / 4275 / 963
Регистрация: 30.01.2014
Сообщений: 7,064
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. Опубликовано тут исключительно в образовательных целях
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.04.2014, 22:00
Привет! Вот еще темы с ответами:

Реализация битовых операций в Си++ - C++
По теме: Реализация битовых операций в Си++. Даны два неравных числа: n и m, не превосходящие 31. Вычислите 2^n+2^m.

Упаковка битовых групп - C++
Доброго времени суток. Подскажите пожалуйста где я ошибся? Задание в шапке проги // File !lab4-2.cpp // Упаковка битовых групп // ...

Обработка битовых последовательности (Срочно) - C++
Решите пожалуйста задачу на с++ НЕ че не могу сделать, голову сломал, напишите плиз а то я у же в очередье на отчисления в универе ...

Выполнение битовых логических операций - C++
Вот такой пример: // BitTest — инициируются две переменные и // выводятся результаты выполнения // операторов ~,&amp;,| и ^ #include...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
01.04.2014, 22:00
Ответ Создать тему
Опции темы

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