@@ -115,13 +115,47 @@ pub const Int = struct {
115
115
return ! r .isOdd ();
116
116
}
117
117
118
- fn bitcount ( self : Int ) usize {
119
- const u_bit_count = (self . len - 1 ) * Limb . bit_count + ( Limb . bit_count - @clz ( self . limbs [ self . len - 1 ]));
120
- return usize ( @boolToInt ( ! self .positive )) + u_bit_count ;
118
+ // Returns the number of bits required to represent the absolute value of self.
119
+ fn bitCountAbs (self : Int ) usize {
120
+ return ( self .len - 1 ) * Limb . bit_count + ( Limb . bit_count - @clz ( self . limbs [ self . len - 1 ])) ;
121
121
}
122
122
123
+ // Returns the number of bits required to represent the integer in twos-complement form.
124
+ //
125
+ // If the integer is negative the value returned is the number of bits needed by a signed
126
+ // integer to represent the value. If positive the value is the number of bits for an
127
+ // unsigned integer. Any unsigned integer will fit in the signed integer with bitcount
128
+ // one greater than the returned value.
129
+ //
130
+ // e.g. -127 returns 8 as it will fit in an i8. 127 returns 7 since it fits in a u7.
131
+ fn bitCountTwosComp (self : Int ) usize {
132
+ var bits = self .bitCountAbs ();
133
+
134
+ // If the entire value has only one bit set (e.g. 0b100000000) then the negation in twos
135
+ // complement requires one less bit.
136
+ if (! self .positive ) block : {
137
+ bits += 1 ;
138
+
139
+ if (@popCount (self .limbs [self .len - 1 ]) == 1 ) {
140
+ for (self .limbs [0 .. self .len - 1 ]) | limb | {
141
+ if (@popCount (limb ) != 0 ) {
142
+ break :block ;
143
+ }
144
+ }
145
+
146
+ bits -= 1 ;
147
+ }
148
+ }
149
+
150
+ return bits ;
151
+ }
152
+
153
+ // Returns the approximate size of the integer in the given base. Negative values accomodate for
154
+ // the minus sign. This is used for determining the number of characters needed to print the
155
+ // value. It is inexact and will exceed the given value by 1-2 digits.
123
156
pub fn sizeInBase (self : Int , base : usize ) usize {
124
- return (self .bitcount () / math .log2 (base )) + 1 ;
157
+ const bit_count = usize (@boolToInt (! self .positive )) + self .bitCountAbs ();
158
+ return (bit_count / math .log2 (base )) + 1 ;
125
159
}
126
160
127
161
pub fn set (self : * Int , value : var ) Allocator.Error ! void {
@@ -189,9 +223,9 @@ pub const Int = struct {
189
223
pub fn to (self : Int , comptime T : type ) ConvertError ! T {
190
224
switch (@typeId (T )) {
191
225
TypeId .Int = > {
192
- const UT = if ( T . is_signed ) @IntType (false , T .bit_count - 1 ) else T ;
226
+ const UT = @IntType (false , T .bit_count ) ;
193
227
194
- if (self .bitcount () > 8 * @sizeOf ( UT ) ) {
228
+ if (self .bitCountTwosComp () > T . bit_count ) {
195
229
return error .TargetTooSmall ;
196
230
}
197
231
@@ -208,9 +242,17 @@ pub const Int = struct {
208
242
}
209
243
210
244
if (! T .is_signed ) {
211
- return if (self .positive ) r else error .NegativeIntoUnsigned ;
245
+ return if (self .positive ) @intCast ( T , r ) else error .NegativeIntoUnsigned ;
212
246
} else {
213
- return if (self .positive ) @intCast (T , r ) else - @intCast (T , r );
247
+ if (self .positive ) {
248
+ return @intCast (T , r );
249
+ } else {
250
+ if (math .cast (T , r )) | ok | {
251
+ return - ok ;
252
+ } else | _ | {
253
+ return @minValue (T );
254
+ }
255
+ }
214
256
}
215
257
},
216
258
else = > {
@@ -1120,24 +1162,61 @@ test "big.int bitcount + sizeInBase" {
1120
1162
var a = try Int .init (al );
1121
1163
1122
1164
try a .set (0b100 );
1123
- debug .assert (a .bitcount () == 3 );
1165
+ debug .assert (a .bitCountAbs () == 3 );
1124
1166
debug .assert (a .sizeInBase (2 ) >= 3 );
1125
1167
debug .assert (a .sizeInBase (10 ) >= 1 );
1126
1168
1169
+ a .negate ();
1170
+ debug .assert (a .bitCountAbs () == 3 );
1171
+ debug .assert (a .sizeInBase (2 ) >= 4 );
1172
+ debug .assert (a .sizeInBase (10 ) >= 2 );
1173
+
1127
1174
try a .set (0xffffffff );
1128
- debug .assert (a .bitcount () == 32 );
1175
+ debug .assert (a .bitCountAbs () == 32 );
1129
1176
debug .assert (a .sizeInBase (2 ) >= 32 );
1130
1177
debug .assert (a .sizeInBase (10 ) >= 10 );
1131
1178
1132
1179
try a .shiftLeft (a , 5000 );
1133
- debug .assert (a .bitcount () == 5032 );
1180
+ debug .assert (a .bitCountAbs () == 5032 );
1134
1181
debug .assert (a .sizeInBase (2 ) >= 5032 );
1135
1182
a .positive = false ;
1136
1183
1137
- debug .assert (a .bitcount () == 5033 );
1184
+ debug .assert (a .bitCountAbs () == 5032 );
1138
1185
debug .assert (a .sizeInBase (2 ) >= 5033 );
1139
1186
}
1140
1187
1188
+ test "big.int bitcount/to" {
1189
+ var a = try Int .init (al );
1190
+
1191
+ try a .set (0 );
1192
+ debug .assert (a .bitCountTwosComp () == 0 );
1193
+
1194
+ // TODO: stack smashing
1195
+ // debug.assert((try a.to(u0)) == 0);
1196
+ // TODO: sigsegv
1197
+ // debug.assert((try a.to(i0)) == 0);
1198
+
1199
+ try a .set (-1 );
1200
+ debug .assert (a .bitCountTwosComp () == 1 );
1201
+ debug .assert ((try a .to (i1 )) == -1 );
1202
+
1203
+ try a .set (-8 );
1204
+ debug .assert (a .bitCountTwosComp () == 4 );
1205
+ debug .assert ((try a .to (i4 )) == -8 );
1206
+
1207
+ try a .set (127 );
1208
+ debug .assert (a .bitCountTwosComp () == 7 );
1209
+ debug .assert ((try a .to (u7 )) == 127 );
1210
+
1211
+ try a .set (-128 );
1212
+ debug .assert (a .bitCountTwosComp () == 8 );
1213
+ debug .assert ((try a .to (i8 )) == -128 );
1214
+
1215
+ try a .set (-129 );
1216
+ debug .assert (a .bitCountTwosComp () == 9 );
1217
+ debug .assert ((try a .to (i9 )) == -129 );
1218
+ }
1219
+
1141
1220
test "big.int string set" {
1142
1221
var a = try Int .init (al );
1143
1222
try a .setString (10 , "120317241209124781241290847124" );
0 commit comments