剑指Offer--046-求1+2+3+...+n 代码分析

    技术2025-01-16  15

    剑指offer 记录

    剑指Offer–046-求1+2+3+…+n

    对文章里面提到的 指针求和公式 比较好奇,研究了一下,明白了其中的原理。

    代码如下

    #include <stdio.h> #include <stdint.h> int rich(int n) { return ( (int)( &((uint8_t (*) [n])0)[1+n][0]) ) >> 1; } int main() { printf("%d\n", rich(10)); return 0; }

    其中最重要的是 return ( (int)( &((uint8_t (*) [n])0)[1+n][0]) ) >> 1; 下面将对此语句进行分解。

    原理介绍:

    内存地址增加是按照字节方式增加,字节数组下标每增加1,则地址也加1数据类型转换右移1位,则可以认为是数值作除2操作二维数组最大空间占用为 arr[m][n]的最大空间占用为m*n求和公式 1+2+3+4+…+n = (1+n)n/2 = (n+0)(n+1)/2 = 0+1+2+3+4+5…+n

    分解: ① (uint8_t (*) [n])0 uint8_t (*) [n] 代表的是一个包含 n 个数值的数组的指针,将0强制转成包含一个包含 n 个数值的数组的指针,则数组的[0][0]位置地址为0,[0][1]的地址为1,以此类推。 ② ((uint8_t (*) [n])0)[1+n][0]) 可以转换为一个二维数组的[n+1][0]位置,则此位置的地址为 (n+1) * n - 基地址 ③ &((uint8_t (*) [n])0)[1+n][0]) 取[n+1][0]的地址,则相对于基地址0而言,则地址就等于(n+1)*n-0 ④ ( (int)( &((uint8_t (*) [n])0)[1+n][0]) ) 强制转换为int类型 ⑤ ( (int)( &((uint8_t (*) [n])0)[1+n][0]) ) >> 1 右移1位,代表除2操作。

    最终取得的数值为 (n+1)*n / 2 和求和公式可以对应上。

    Processed: 0.008, SQL: 9