Двоичное представление целых чисел степеней 2 - PullRequest
Новая
       3

Двоичное представление целых чисел степеней 2

0 голосов
/ 01 декабря 2018

У меня проблема с интерпретацией двоичного считывания чисел, хранящегося в памяти компьютера.

Я написал небольшую программу , которая принимает целое число, число с плавающей запятой или строку и печатаетдвоичное число, хранящееся в памяти.

После этого я хотел посмотреть игру между десятичным и двоичным числами.Это привело к итерации степеней 2 от 0 до 64. Чтобы напечатать двоичную часть, я использовал раздел программы выше.То, что я нашел, было для меня странным, и я не могу понять, почему система хранит числа такими, какие они есть.

Вот мое замешательство: для каждой итерации программа печатает десятичную и двоичную версиииз 3 чисел как таковых:

  • 1 << i: </li>
  • 1 << i - 1: </li>
  • 1 << i (со всеми установленными меньшими битамидо 1): </li>

Когда программа достигает 30, вот 6 выходов: 30: 1073741824 30: 1073741823 30: 2147483647 00000000 00000000 00000000 01000000 00000000 00000000 00000000 00000000 11111111 11111111 11111111 00111111 00000000 00000000 00000000 00000000 11111111 11111111 11111111 01111111 00000000 00000000 00000000 00000000

При 31 это происходит: 31: 18446744071562067968 31: 2147483647 31: 18446744073709551615 00000000 00000000 00000000 10000000 11111111 11111111 11111111 11111111 11111111 11111111 11111111 01111111 00000000 00000000 00000000 00000000 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

И это в 32: 32: 1 32: 0 32: 18446744073709551615 00000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

Запрос

Может ли кто-нибудь помочь мне интерпретировать эти выводы, включая объяснение, почему биты не продолжают хорошо сдвигаться до 18446744073709551615 (2 ^ 64)- 1) достигнуто?

(Я также приветствовал бы любые предложения по программе.)

Ссылки

Так что вы можете играть дома, вот программа ивывод, который он мне дал:

Эталонная программа 

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

void dtob(char *num, size_t size)
{
    int i;
    bool binary;

    for ( ; size; size--, num++) {
        for (i = 7; i > -1; i--) {
            binary = *num & (1 << i);
            printf("%d", binary);

        }
        printf(" ");
    }
    printf("\n");
}

int main(void)
{
    int i;

    uintmax_t num1 = 0;
    uintmax_t num2 = 0;
    uintmax_t num3 = 0;

    void *ptr1;
    void *ptr2;
    void *ptr3;

    ptr1 = &num1;
    ptr2 = &num2;
    ptr3 = &num3;

    for (i = 0; i < 65; i++) {
        num1 = (1 << i);
        num2 = (1 << i) - 1;
        num3 |= (1 << i);

        printf("%d: %ju\n", i, num1);
        printf("%d: %ju\n", i, num2);
        printf("%d: %ju\n", i, num3);

        dtob(ptr1, sizeof(uintmax_t));
        dtob(ptr2, sizeof(uintmax_t));
        dtob(ptr3, sizeof(uintmax_t));
    }

    return 0;
}

Эталонный вывод: 

0: 1
0: 0
0: 1
00000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
1: 2
1: 1
1: 3
00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000011 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
2: 4
2: 3
2: 7
00000100 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000011 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
3: 8
3: 7
3: 15
00001000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00001111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
4: 16
4: 15
4: 31
00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00001111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00011111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
5: 32
5: 31
5: 63
00100000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00011111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
6: 64
6: 63
6: 127
01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
01111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
7: 128
7: 127
7: 255
10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
01111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
8: 256
8: 255
8: 511
00000000 00000001 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000001 00000000 00000000 00000000 00000000 00000000 00000000 
9: 512
9: 511
9: 1023
00000000 00000010 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000001 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000011 00000000 00000000 00000000 00000000 00000000 00000000 
10: 1024
10: 1023
10: 2047
00000000 00000100 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000011 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000111 00000000 00000000 00000000 00000000 00000000 00000000 
11: 2048
11: 2047
11: 4095
00000000 00001000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00001111 00000000 00000000 00000000 00000000 00000000 00000000 
12: 4096
12: 4095
12: 8191
00000000 00010000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00001111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00011111 00000000 00000000 00000000 00000000 00000000 00000000 
13: 8192
13: 8191
13: 16383
00000000 00100000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00011111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00111111 00000000 00000000 00000000 00000000 00000000 00000000 
14: 16384
14: 16383
14: 32767
00000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00111111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 01111111 00000000 00000000 00000000 00000000 00000000 00000000 
15: 32768
15: 32767
15: 65535
00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 01111111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000000 00000000 00000000 00000000 00000000 00000000 
16: 65536
16: 65535
16: 131071
00000000 00000000 00000001 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000001 00000000 00000000 00000000 00000000 00000000 
17: 131072
17: 131071
17: 262143
00000000 00000000 00000010 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000001 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000011 00000000 00000000 00000000 00000000 00000000 
18: 262144
18: 262143
18: 524287
00000000 00000000 00000100 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000011 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000111 00000000 00000000 00000000 00000000 00000000 
19: 524288
19: 524287
19: 1048575
00000000 00000000 00001000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00001111 00000000 00000000 00000000 00000000 00000000 
20: 1048576
20: 1048575
20: 2097151
00000000 00000000 00010000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00001111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00011111 00000000 00000000 00000000 00000000 00000000 
21: 2097152
21: 2097151
21: 4194303
00000000 00000000 00100000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00011111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00111111 00000000 00000000 00000000 00000000 00000000 
22: 4194304
22: 4194303
22: 8388607
00000000 00000000 01000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00111111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 01111111 00000000 00000000 00000000 00000000 00000000 
23: 8388608
23: 8388607
23: 16777215
00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 01111111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000000 00000000 00000000 00000000 00000000 
24: 16777216
24: 16777215
24: 33554431
00000000 00000000 00000000 00000001 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000001 00000000 00000000 00000000 00000000 
25: 33554432
25: 33554431
25: 67108863
00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000001 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000011 00000000 00000000 00000000 00000000 
26: 67108864
26: 67108863
26: 134217727
00000000 00000000 00000000 00000100 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000011 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000111 00000000 00000000 00000000 00000000 
27: 134217728
27: 134217727
27: 268435455
00000000 00000000 00000000 00001000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00001111 00000000 00000000 00000000 00000000 
28: 268435456
28: 268435455
28: 536870911
00000000 00000000 00000000 00010000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00001111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00011111 00000000 00000000 00000000 00000000 
29: 536870912
29: 536870911
29: 1073741823
00000000 00000000 00000000 00100000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00011111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00111111 00000000 00000000 00000000 00000000 
30: 1073741824
30: 1073741823
30: 2147483647
00000000 00000000 00000000 01000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00111111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 01111111 00000000 00000000 00000000 00000000 
31: 18446744071562067968
31: 2147483647
31: 18446744073709551615
00000000 00000000 00000000 10000000 11111111 11111111 11111111 11111111 
11111111 11111111 11111111 01111111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
32: 1
32: 0
32: 18446744073709551615
00000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
33: 2
33: 1
33: 18446744073709551615
00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
34: 4
34: 3
34: 18446744073709551615
00000100 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000011 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
35: 8
35: 7
35: 18446744073709551615
00001000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
36: 16
36: 15
36: 18446744073709551615
00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00001111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
37: 32
37: 31
37: 18446744073709551615
00100000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00011111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
38: 64
38: 63
38: 18446744073709551615
01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
39: 128
39: 127
39: 18446744073709551615
10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
01111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
40: 256
40: 255
40: 18446744073709551615
00000000 00000001 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
41: 512
41: 511
41: 18446744073709551615
00000000 00000010 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000001 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
42: 1024
42: 1023
42: 18446744073709551615
00000000 00000100 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000011 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
43: 2048
43: 2047
43: 18446744073709551615
00000000 00001000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00000111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
44: 4096
44: 4095
44: 18446744073709551615
00000000 00010000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00001111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
45: 8192
45: 8191
45: 18446744073709551615
00000000 00100000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00011111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
46: 16384
46: 16383
46: 18446744073709551615
00000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 00111111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
47: 32768
47: 32767
47: 18446744073709551615
00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 01111111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
48: 65536
48: 65535
48: 18446744073709551615
00000000 00000000 00000001 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
49: 131072
49: 131071
49: 18446744073709551615
00000000 00000000 00000010 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000001 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
50: 262144
50: 262143
50: 18446744073709551615
00000000 00000000 00000100 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000011 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
51: 524288
51: 524287
51: 18446744073709551615
00000000 00000000 00001000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00000111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
52: 1048576
52: 1048575
52: 18446744073709551615
00000000 00000000 00010000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00001111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
53: 2097152
53: 2097151
53: 18446744073709551615
00000000 00000000 00100000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00011111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
54: 4194304
54: 4194303
54: 18446744073709551615
00000000 00000000 01000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 00111111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
55: 8388608
55: 8388607
55: 18446744073709551615
00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 01111111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
56: 16777216
56: 16777215
56: 18446744073709551615
00000000 00000000 00000000 00000001 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
57: 33554432
57: 33554431
57: 18446744073709551615
00000000 00000000 00000000 00000010 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000001 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
58: 67108864
58: 67108863
58: 18446744073709551615
00000000 00000000 00000000 00000100 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000011 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
59: 134217728
59: 134217727
59: 18446744073709551615
00000000 00000000 00000000 00001000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00000111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
60: 268435456
60: 268435455
60: 18446744073709551615
00000000 00000000 00000000 00010000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00001111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
61: 536870912
61: 536870911
61: 18446744073709551615
00000000 00000000 00000000 00100000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00011111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
62: 1073741824
62: 1073741823
62: 18446744073709551615
00000000 00000000 00000000 01000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 00111111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
63: 18446744071562067968
63: 2147483647
63: 18446744073709551615
00000000 00000000 00000000 10000000 11111111 11111111 11111111 11111111 
11111111 11111111 11111111 01111111 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 
64: 1
64: 0
64: 18446744073709551615
00000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

ThaЗаранее спасибо!Хильда

1 Ответ

0 голосов
/ 01 декабря 2018

Код смещается за пределы допустимого диапазона. 

uintmax_t num1;
for (i = 0; i < 65; i++) {
    num1 = (1 << i);         // int overflow! UB

Если int 32-битный, 1 << 31 равен неопределенное поведение (UB), сдвигая 1 в положительный знакбит.

Использование 1u помогает избежать этого в случае i==31.

И все же сдвигается как 32,33,34, ... когда unsigned - это 32-битные результатыв UB.

Используйте более широкий 1, такой как 1LLU, который составляет не менее 64 бит.

Код все еще выходит за пределы допустимого диапазона. 

uintmax_t num1;
for (i = 0; i < 65; i++) {
    num1 = (1LLU << i);  // trouble when i==64

Если unsigned long long 64-битный, 1LLU << 64 UB.

Использование более широкого 1, например, UINTMAX_C(1) может быть шире, чем 64 бит, но маловероятно в2018.

Мораль истории:

  • Убедитесь, что целочисленная математика соответствует типу целевого объекта. 

    uintmax_t num1;
num1 = UINTMAX_C(1) << i;
// or     
uintmax_t one = 1;
num1 = one << i;
// or when `num1` has a value
num1 = (num1*0 + 1) << i;  // let the compiler optimize

  • Не сдвигать шире, чем ширина шрифта.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...