Solidity - 使用位运算节省 gas

• 原文：https://hackmd.io/@fiveoutofnine/Skl9eRbX9
• 译文出自：登链翻译计划
• 译者：翻译小组
• 校对：Tiny 熊
• 本文永久链接：learnblockchain.cn/article…

在以太坊上进行交易是非常昂贵的，所以有时候，对代码进行更细粒度的控制是有意义的。有一种使用位操作的方法，除了可以优化 gas ，本身也是非常有用的。我在推特@fiveoutofnine上发布了一些有趣的技巧:

• quick/small mapping
• bitpacking consecutive data to reduce storage costs
• if blocks with 3 bit operations
• basic operations
• loop through some numbers without an array +extra

这些操作/技巧与其他方面的编码非常不同，所以对于没有经验的人来说可能相当深奥。虽然我在每条Tweet都包含一个应用程序示例，但仍然很难明白在哪里/如何应用它们。我有一个项目是一个很好的例子——链上国际象棋引擎，但是对于初学者来说，它的合约可能有点难。

而在这篇文章中，我将解释其中的一些技巧，并通过一款更简单的井字棋游戏来分享我的思考过程。

基础位运算

首先，了解在井字游戏例子中使用的基础位操作:>>, <<, &, |, 和 ^。如果您已经很熟悉了，可以跳过这一节!

右移： >> (SHR)

二进制位全部向右移，参考位运算说明

例：1010 >> 1 = 101 (十进制: 10 >> 1 = 5)

注意：将一个整数$m$向右移$n$位，结果为$\lfloor\frac{m}{2^n}\rfloor$。

左移：<< (SHL)

二进制位全部向左移

例：1010 << 2 = 101000 (十进制: 10 << 2 = 40).

注意：将一个整数$m$向左移$n$位，结果为$m\cdot2^n$。

与：& (AND)

按位与是一种二进制运算，它取两个相等长度的二进制，并对对应位进行逻辑与运算。因此，如果两个位都是1，则二进制表示的结果位是1 (1 × 1 = 1);否则，结果为0 (1 × 0 = 0 并且 0 × 0 = 0)。

例:

0101 (十进制: 5)
& 0011 (十进制: 3)
= 0001 (十进制: 1).

注意： 因为&只有在两个数的位都是1的情况下才“接受”位，所以你可以构造一个掩码来选择你想要读取的数字的哪个位。例如，对于一些数字$m$，如果我们想要读取每一位，我们可以计算 m & 1010...1010。

或：| (OR)

按位或是一种二进制运算，它取两个长度相等的位串，并对对应位进行逻辑或运算。如果两个位都为0，则结果为0，否则结果为1。

例:

0101 (十进制: 5)
| 0011 (十进制: 3)
= 0111 (十进制: 7)

注意：因为 | 只要其中一个数的位是1就会“接受”这个位，你可以把一个数字的位写入另一个数字，只要第一个数字在对应位置的位都是0。

异或：^ (XOR)

按位异或是一种二进制运算，它取两个长度相等的位串，并对对应位进行执行逻辑异或操作。如果只有一个位是1，那么结果是1，但是如果两个都是0或者两个都是1，那么结果就是0。这样，我们可以对两个位进行比较，如果两个位不同则为1，相同则为0。

例:

0101 (十进制: 5)
^ 0011 (十进制: 3)
= 0110 (十进制: 6)

注意：当用另一组位重写一个数的位时，将^、&和|结合起来用会很有帮助。例如，假设我们想用101重写10010的最后3位（如010):

• 首先，我们用^构造一个掩码来选择我们需要的位（除了最后3位的所有位）：11111 ^ 00111 = 11000
• 接下来，我们用&“删除”（用0替代）10010的最后三位: 10010 & (11000) = 10000
• 最后，我们用|写入101: 10000 | 00101 = 10101
• 综合起来， (10010 & (1111 ^ 111)) | 101 = 101010

注意：除非特别说明，本节中的0和1都是二进制表示。

接下来，通过示例和注释来了解一些基本方法!

井字棋

在写合约之前，我们先列出井字棋游戏所需的基础要点。这是一款2人游戏，每个玩家只有一种落子(输入)方式(将自己的棋子符号放在一个空的格子中)。当玩家落子(输入)时，我们需要验证以下几点:

• 玩家是这个游戏中两个玩家中的一个
• 轮到这个玩家下一步棋了

接下来，我们需要确认这次落子是合规的。

最后，要确认游戏是否已经结束了(一个玩家的3个棋子连城了直线)。

把上面的验证用伪代码写在函数playMove中：

function playMove(position):
// Player validation
if ("player is not one of the 2 in the game")
    revert Error();
if ("it is not the player's turn")
    revert Error();

// Move validation
if ("the position has already been played in the board")
    revert Error();

applyMove(position)

// Game ending scenario
if ("either player has formed 3 consecutive dots")
    ("set the winner and end the game")

棋盘/游戏状态的表示

现在我们对要存储的信息有了一个概念，让我们用代码来表示。请记住，设计应该考虑计算的高效: 代码将读取数据并计算，如访问、解码和存储等操作都应该便宜。我们可以期望使用尽可能少的位，毕竟在EVM上存储成本是很高的(通常)。

初级的表示方法

下面是一个很初级的方法：

struct Game {
    uint8[9] board; // 0 = empty, 1 = player 0, 2 = player 1
    bool turn; // false = player 0, true = player 1
    bool hasGameEnded;
    bool playerZeroWon; // only set if `hasGameEnded` is true
    bool playerOneWon; // only set if `hasGameEnded` is true
    address playerZero;
    address playerOne;
}

uint8[9] board会存在很多不必要的读写，我们并不需要8位来存储数据；因为只有3个有效的状态，只需要2位（$ 2^2=4$）就够了。而bool turn 只需要1位：false为0，true为1。最后，因为bool hasGameEnded, bool playerZeroWon, 和 bool playerOneWon应该合在一起作为游戏状态的表示（只有4种可能性），我们可以将它们组合为2位：

• 游戏还在继续 (00),
• 玩家0赢了 (10),
• 玩家1赢了 (11),
• 平局 (01).

我们总共只用了21位（使用上面的结构时：$ 8\cdot9+8+8+8+8=104$）来表示所有事情：

[000000000000000000][00][0]
• First 2 * 9 = 18 bits denote the board
• Next 2 bits denote whether game is ongoing
• Last bit denotes whose turn it is to play

不要用结构体，将游戏数据位打包(Bitpack)进uint256

如果我们用结构体，就必须用uint24。取而代之，我们将玩家的地址分别存储在两个映射中，并将游戏数据存储在第三个映射中:

mapping(uint256 => address) public playerZeros;
mapping(uint256 => address) public playerOnes;
mapping(uint256 => uint256) public games;

这样通过对连续的游戏数据进行位打包（Bitpack），我们可以更便宜地存储游戏数据。这个方法是为了尽可能地减少写入零槽(zero slot)的次数(指写入新数据)，因为向零槽写入需要花费20k gas，而向非零槽写入只需要5k gas（修改数据）。我们将很多游戏数据位打包成uint256（这时，$\lfloor\frac{256}{21}\rfloor=12$，所以我们可以用一个uint256容纳12次游戏）。这种方法，只需要每第12次游戏存储花20K gas，而其他次游戏则只需要花5k gas。读写都很高效:

// Each `uint256` value has 12 games bitpacked into it.
mapping(uint256 => uint256) public gameStates;

// Each game is 21 bits, so the desired mask is
// `0b111111111111111111111 = 0x1FFFFF` (21 `1`s).
uint256 internal constant GAME_MASK = 0x1FFFFF;

function retrieveGame(uint256 _gameId) external view returns (uint256) {
// Divide by 12 and take mod 12 because 12 games are bit packed into
// each `uint256`.
uint256 key = _gameId / 12;
uint256 index = _gameId % 12;

// Bit shift by `21 * index` to get to the desired game.
return (gameStates[key] >> (21 * index)) & GAME_MASK;
}

function writeGame(uint256 _gameId, uint256 _gameState) external {
uint256 key = _gameId / 12;
uint256 index = _gameId % 12;

// Read the entire `uint256` into memory first because it's cheaper to make all
// modifications in memory before writing the final result to storage.
uint256 gameUint256 = gameStates[key];

// This process overwrites whatever exists in the desired 21 bit slot with
// `_gameState` (see `XOR` in "Basic Bit Operations").
gameUint256 &= type(uint256).max ^ (GAME_MASK << (index * 21));
gameUint256 |= _gameState << (index * 21);

// Write to storage.
gameStates[key] = gameUint256;
}

最终的表示方法

现在，我们有3个映射来跟踪所有的游戏数据和玩家。基于这种设置，将每次新游戏存储到存储空间所需的成本大约平均为$ 20000+20000+\frac{20000+5000\cdot12}{13}\approx46154$ gas（2个玩家地址需2次写入零槽，写入游戏状态数据大约需 6154 gas）。

然而，由于地址只有160位，我们可以将游戏状态与其中一个玩家的地址进行位打包来减少一次写入存储。我们选玩家0的地址，如下:

// The first 21 bits are games' data, and the remaining 160 bits are player 0
// addresses.
mapping(uint256 => uint256) public playerZerosAndGames;
mapping(uint256 => address) public playerOnes;

再次，读写都更高效：

uint256 internal currentGameId;

function createNewGame(address _playerZero, address _playerOne) {
uint256 gameId = currentGameId++;
// The first 21 bits are the game. We don't need to set anything for this
// because the all bits are 0 for the starting position.
playerZerosAndGames[gameId] = uint256(uint160(_playerZero));
playerOnes[gameId] = _playerOne;
}

function retrieveGame(uint256 _gameId) external view returns (uint256) {
return playerZerosAndGames[_gameId] >> 160;
}

function writeGame(uint256 _gameId, uint256 _gameState) external {
uint160 playerZero = uint160(playerZerosAndGames[_gameId]);
// Bit shift `_gameState` left by 160 to make space for player 0's address.
playerZerosAndGames[_gameId] = (_gameState << 160) | playerZero;
}

注意：在这种特殊情况下，因为无论如何每个新游戏都至少需要2个存储槽(2个玩家地址会超过1个32字节的字)，所以削减用于表示游戏数字的位数是不必要的——其他条件都相同，用96位（256-160=96）同样高效。不过，我还是想在这里描述一下这个过程，它可能也有适用的时候。

微调表示方法

对于井字游戏来说，上面的表示方法已经足够好了。但对不同的应用程序，可能需要额外的考虑。这些需要就具体情况来看，以下是一些常见的情况:

经常访问的数据

将经常访问的$n$位放在最前面/最后面可能有助于优化计算:只需要一个>>或者& 来访问。因此，如果某些信息需要比其他信息更频繁地访问，那么将其放置在开始/结束位置可能是明智的。

通过结构化数据减少计算(使用值本身!)

EVM上一个开销很大的计算是switch语句。记住这一点，通过结构化数据来代替它们可能是明智的。例如，假设有3位portion需要映射到8个不同的输出:

if      (portion == 0) return  3;
else if (portion == 1) return  7;
else if (portion == 2) return 12;
else if (portion == 3) return  6;
else if (portion == 4) return 13;
else if (portion == 5) return  9;
else if (portion == 6) return  3;
else                   return 15;

相反，你可以使用`por...