888 |
888 |
889 bitCount |
889 bitCount |
890 "return the number of 1-bits in the receiver" |
890 "return the number of 1-bits in the receiver" |
891 |
891 |
892 %{ /* NOCONTEXT */ |
892 %{ /* NOCONTEXT */ |
893 int _cnt = 0; |
893 unsigned int _cnt; |
894 int _self = __intVal(self); |
894 unsigned INT _self = __intVal(self); |
895 |
895 |
|
896 #define ALGORIHTM_3 |
|
897 |
|
898 #ifdef ALGORITHM_1 |
|
899 // old k&r code; might be better if only one or two bits are set |
|
900 |
|
901 _cnt = 0; |
896 while (_self) { |
902 while (_self) { |
897 _cnt++; |
903 _cnt++; |
898 _self = _self & (_self - 1); |
904 _self = _self & (_self - 1); |
899 } |
905 } |
|
906 #else |
|
907 # ifdef ALGORITHM_2 |
|
908 // seems to be faster on the average (and has better worst case) |
|
909 |
|
910 static unsigned char table[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; |
|
911 |
|
912 _cnt = 0; |
|
913 while (_self) { |
|
914 _cnt += table[ _self & 0x0F ]; |
|
915 _self >>= 4; |
|
916 } |
|
917 # else |
|
918 # ifdef ALGORIHTM_3 |
|
919 // the fastest, but hard (impossible) to understand (google for fastest bit count) |
|
920 # if __POINTER_SIZE__ == 8 |
|
921 unsigned int _v1, _v2; |
|
922 |
|
923 _v1 = _self & 0xFFFFFFFF; |
|
924 _v1 = _v1 - ((_v1 >> 1) & 0x55555555); |
|
925 _v1 = (_v1 & 0x33333333) + ((_v1 >> 2) & 0x33333333); |
|
926 _v1 = ((_v1 + (_v1 >> 4)) & 0x0F0F0F0F); |
|
927 |
|
928 _v2 = (unsigned int)(_self >> 32); |
|
929 _v2 = _v2 - ((_v2 >> 1) & 0x55555555); |
|
930 _v2 = (_v2 & 0x33333333) + ((_v2 >> 2) & 0x33333333); |
|
931 _v2 = ((_v2 + (_v2 >> 4)) & 0x0F0F0F0F); |
|
932 |
|
933 _cnt = ((_v1 * 0x01010101) >> 24) + ((_v2 * 0x01010101) >> 24); |
|
934 # else |
|
935 _cnt = _self - ((_self >> 1) & 0x55555555); |
|
936 _cnt = (_cnt & 0x33333333) + ((_cnt >> 2) & 0x33333333); |
|
937 _cnt = ((_cnt + (_cnt >> 4)) & 0x0F0F0F0F); |
|
938 _cnt = (_cnt * 0x01010101) >> 24; |
|
939 # endif |
|
940 # else |
|
941 error error error |
|
942 # endif |
|
943 # endif |
|
944 #endif |
900 |
945 |
901 RETURN ( __MKSMALLINT(_cnt)); |
946 RETURN ( __MKSMALLINT(_cnt)); |
902 %} |
947 %} |
903 |
948 |
904 " |
949 " |
905 1 to:100000 do:[:n | |
950 1 to:1000000 do:[:n | |
|
951 self assert:(n bitCount = ((n printStringRadix:2) occurrencesOf:$1)) |
|
952 ]. |
|
953 |
|
954 #( |
|
955 16r00010000 16r00100000 16r01000000 16r10000000 |
|
956 16r00020000 16r00200000 16r02000000 16r20000000 |
|
957 16r00040000 16r00400000 16r04000000 16r40000000 |
|
958 16r00080000 16r00800000 16r08000000 16r80000000 |
|
959 |
|
960 16rFFFFFFFF 16r7FFFFFFF 16r3FFFFFFF 16r1FFFFFFF |
|
961 16rEEEEEEEE 16r7EEEEEEE 16r3EEEEEEE 16r1EEEEEEE |
|
962 16rDDDDDDDD 16r7DDDDDDD 16r3DDDDDDD 16r1DDDDDDD |
|
963 16rCCCCCCCC 16r7CCCCCCC 16r3CCCCCCC 16r1CCCCCCC |
|
964 ) do:[:n | |
906 self assert:(n bitCount = ((n printStringRadix:2) occurrencesOf:$1)) |
965 self assert:(n bitCount = ((n printStringRadix:2) occurrencesOf:$1)) |
907 ] |
966 ] |
908 " |
967 |
|
968 1 to:10000000 do:[:n | |
|
969 (n bitCount) |
|
970 ] |
|
971 " |
|
972 |
|
973 "Modified: / 09-01-2012 / 19:12:41 / cg" |
909 ! |
974 ! |
910 |
975 |
911 bitInvert |
976 bitInvert |
912 "return the value of the receiver with all bits inverted" |
977 "return the value of the receiver with all bits inverted" |
913 |
978 |
3889 %}. |
3954 %}. |
3890 ^ super odd |
3955 ^ super odd |
3891 |
3956 |
3892 ! |
3957 ! |
3893 |
3958 |
|
3959 parityOdd |
|
3960 "return true, if an odd number of bits are set in the receiver, false otherwise. |
|
3961 (i.e. true for odd parity) |
|
3962 Undefined for negative values (smalltalk does not require the machine to use 2's complement)" |
|
3963 |
|
3964 %{ /* NOCONTEXT */ |
|
3965 |
|
3966 // tricky, but very fast (google for it, to understand) |
|
3967 #if __POINTER_SIZE__ == 4 |
|
3968 unsigned int v = __intVal(self); |
|
3969 |
|
3970 v ^= v >> 16; |
|
3971 v ^= v >> 8; |
|
3972 v ^= v >> 4; |
|
3973 v &= 0xf; |
|
3974 RETURN ( ( (0x6996 >> v) & 1 ) ? true : false ); |
|
3975 #endif |
|
3976 %}. |
|
3977 ^ super parityOdd |
|
3978 |
|
3979 " |
|
3980 self assert: |
|
3981 (((0 to:255) collect:[:i | i parityOdd ifTrue:1 ifFalse:0]) |
|
3982 asByteArray collect:[:c | c + $0 asciiValue]) asString |
|
3983 = |
|
3984 '0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110' |
|
3985 |
|
3986 self assert:(16r0FFFFFFF parityOdd = 16r0FFFFFFF bitCount odd). |
|
3987 self assert:(16r1FFFFFFF parityOdd = 16r1FFFFFFF bitCount odd). |
|
3988 self assert:(16r3FFFFFFF parityOdd = 16r3FFFFFFF bitCount odd). |
|
3989 self assert:(16r7FFFFFFF parityOdd = 16r7FFFFFFF bitCount odd). |
|
3990 self assert:(16rFFFFFFFF parityOdd = 16rFFFFFFFF bitCount odd). |
|
3991 " |
|
3992 |
|
3993 "Modified (comment): / 09-01-2012 / 19:55:37 / cg" |
|
3994 ! |
|
3995 |
3894 positive |
3996 positive |
3895 "return true, if the receiver is not negative |
3997 "return true, if the receiver is not negative |
3896 reimplemented here for speed" |
3998 reimplemented here for speed" |
3897 |
3999 |
3898 %{ /* NOCONTEXT */ |
4000 %{ /* NOCONTEXT */ |