[發明專利]一種整數取模運算方法、裝置及終端設備

在審

• 申請號: 202011359605.1
• 申請日: 2020-11-27
• 公開（公告）號: CN112363687A
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 劉君
• 申請（專利權）人: OPPO廣東移動通信有限公司
• 主分類號: G06F7/38
• 分類號: G06F7/38
• 代理公司: 廣州德科知識產權代理有限公司 44381
• 代理人: 萬振雄;楊中強

1.一種整數取模運算方法，其特征在于，包括：

將二進制形式的整數b表示為目標形式，所述目標形式包括：2ⁿ-p的形式，和/或，2^n-1+p的形式，其中，n為所述整數b的位寬，0≤p≤2^n-2，n大于或等于1；

計算整數a對所述目標形式的所述整數b取模的取模結果。

2.根據權利要求1所述的方法，其特征在于，所述將二進制形式的整數b表示為目標形式，包括：

將所述整數b表示為b＝2ⁿ-p，0≤p2^n-1。

3.根據權利要求1所述的方法，其特征在于，所述將二進制形式的整數b表示為目標形式，包括：

將所述整數b表示為b＝2^n-1+p，0≤p2^n-1。

4.根據權利要求1所述的方法，其特征在于，所述將二進制形式的整數b表示為目標形式，包括：

所述整數b的次高位為1時，所述整數b表示為b＝2ⁿ-p，1≤p≤2^n-2；

所述整數b的次高位為0時，所述整數b表示為b＝2^n-1+p，0≤p2^n-2。

5.根據權利要求1所述的方法，其特征在于，所述計算整數a對目標形式的所述整數b取模的取模結果，包括：

將二進制形式的整數a作為被除數；

將所述被除數從最低位開始拆分為S段，得到各段表示的整數其中，m為a的位寬，0≤i≤S-2，其中，為n或者n-1；

將各段表示的整數和所述整數b，計算所述整數a的同余式

根據所述被除數的同余式確定所述整數a對所述整數b取模的取模結果。

6.根據權利要求5所述的方法，其特征在于，所述將各段表示的整數和所述整數b，計算所述被除數的同余式包括：

將所述各段表示的整數對所述整數b取模，得到所述各段表示的整數對應的取模結果；

將所述各段表示的整數對應的取模結果，根據權值進行加權運算，得到所述被除數的同余式

7.根據權利要求5所述的方法，其特征在于，若所述大于0，則所述根據所述被除數的同余式確定所述整數a對所述整數b取模的取模結果，包括：

若則確定所述取模結果為0；

若則確定所述取模結果為

若則確定所述取模結果為

若將所述作為所述被除數，并執行所述將所述被除數從最低位開始拆分為S段的步驟，直到所述被除數的同余式小于或等于2b，以得到取模結果。

8.根據權利要求5所述的方法，其特征在于，若所述小于0，則所述根據所述被除數的同余式確定所述整數a對所述整數b取模的取模結果，包括：

若則確定所述取模結果為0；

若則確定所述取模結果為

若則確定所述取模結果為

若將所述作為所述被除數，并執行所述將所述被除數從最低位開始拆分為S段的步驟，直到所述被除數的同余式小于或等于2b，以得到取模結果。

9.根據權利要求5所述的方法，其特征在于，所述權值為或者其中，為1或-1。

10.根據權利要求9所述的方法，其特征在于，

若所述整數b表示為b＝2ⁿ-p，1≤p≤2^n-2，則所述權值為pⁱ或者pⁱ mod b；

或者，

若所述整數b表示為b＝2^n-1+p，0≤p2^n-2，則所述權值為(-1)ⁱ·pⁱ或者(-1)ⁱ·(pⁱ modb)。