Bitwise operations
You are encouraged to solve this task according to the task description, using any language you may know.
Basic Data Operation
This is a basic data operation. It represents a fundamental action on a basic data type.
You may see other such operations in the Basic Data Operations category, or:
Integer Operations
Arithmetic |
Comparison
Boolean Operations
Bitwise |
Logical
String Operations
Concatenation |
Interpolation |
Comparison |
Matching
Memory Operations
Pointers & references |
Addresses
Write a function to perform a bitwise AND, OR, and XOR on two integers, a bitwise NOT on the first integer, a left shift, right shift, right arithmetic shift, left rotate, and right rotate. All shifts and rotates should be done on the first integer with a shift/rotate amount of the second integer. If any operation is not available in your language, note it.
Ada
The following program performs all required operations and prints the resulting values in base 2 for easy checking of the bit values.
<ada> with Ada.Text_Io; use Ada.Text_Io; with Interfaces; use Interfaces;
procedure Bitwise is subtype Byte is Unsigned_8; package Byte_Io is new Ada.Text_Io.Modular_Io(Byte); A : Byte := 255; B : Byte := 170; X : Byte := 128; N : Natural := 1;
begin
Put_Line("A and B = "); Byte_Io.Put(Item => A and B, Base => 2);
Put_Line("A or B = "); Byte_IO.Put(Item => A or B, Base => 2);
Put_Line("A xor B = "); Byte_Io.Put(Item => A xor B, Base => 2);
Put_Line("Not A = "); Byte_IO.Put(Item => not A, Base => 2);
New_Line(2);
Put_Line(Unsigned_8'Image(Shift_Left(X, N))); -- Left shift
Put_Line(Unsigned_8'Image(Shift_Right(X, N))); -- Right shift
Put_Line(Unsigned_8'Image(Shift_Right_Arithmetic(X, N))); -- Right Shift Arithmetic
Put_Line(Unsigned_8'Image(Rotate_Left(X, N))); -- Left rotate
Put_Line(Unsigned_8'Image(Rotate_Right(X, N))); -- Right rotate
end bitwise;</ada>
ALGOL 68
main:(
PRIO ROL = 8, ROR = 8; # ROL and ROR are not built in, define and overload them here #
OP ROL = (BITS b, INT rotate) BITS: b SHL rotate OR b SHR ( bits width - rotate );
OP ROR = (BITS b, INT rotate) BITS: b SHR rotate OR b SHL ( bits width - rotate );
OP ROL = (LONG BITS b, INT rotate) LONG BITS: b SHL rotate OR b SHR ( long bits width - rotate );
OP ROR = (LONG BITS b, INT rotate) LONG BITS: b SHR rotate OR b SHL ( long bits width - rotate );
OP ROL = (LONG LONG BITS b, INT rotate) LONG LONG BITS: b SHL rotate OR b SHR ( long long bits width - rotate );
OP ROR = (LONG LONG BITS b, INT rotate) LONG LONG BITS: b SHR rotate OR b SHL ( long long bits width - rotate );
PROC bitwise = (BITS a, BITS b, INT shift)VOID:
(
printf((
$" bits shorths: "gxgl$, bits shorths, "1 plus the number of extra SHORT BITS types",
$" bits lengths: "gxgl$, bits lengths, "1 plus the number of extra LONG BITS types",
$" max bits: "gl$, max bits,
$" long max bits: "gl$, long max bits,
$" long long max bits: "gl$, long long max bits,
$" bits width: "gxgl$, bits width, "The number of CHAR required to display BITS",
$" long bits width: "gxgl$, long bits width, "The number of CHAR required to display LONG BITS",
$" long long bits width: "gxgl$, long long bits width, "The number of CHAR required to display LONG LONG BITS",
$" bytes shorths: "gxgl$, bytes shorths, "1 plus the number of extra SHORT BYTES types",
$" bytes lengths: "gxgl$, bits lengths, "1 plus the number of extra LONG BYTES types",
$" bytes width: "gxgl$, bytes width, "The number of CHAR required to display BYTES",
$" long bytes width: "gxgl$, long bytes width, "The number of CHAR required to display LONG BYTES"
));
printf(($" a: "gl$,a));
printf(($" b: "gl$,b));
printf(($" a and b: "gl$, a AND b));
printf(($" a or b: "gl$, a OR b));
printf(($" a xor b: "gl$, a XOR b));
printf(($" not b: "gl$, NOT a));
printf(($" a shl "d": "gl$, shift, a SHL shift));
printf(($" a shr "d": "gl$, shift, a SHR shift));
printf(($" a rol "d": "gl$, shift, a ROL shift));
printf(($" a ror "d": "gl$, shift, a ROR shift))
COMMENT with original ALGOL 68 character set;
printf(($" a and b: "gl$, a ∧ b));
printf(($" a or b: "gl$, a ∨ b));
printf(($" not b: "gl$, ¬ a));
printf(($" a shl "d": "gl$, shift, a ↑ shift));
printf(($" a shr "d": "gl$, shift, a ↓ shift));
Also:
printf(($" a and b: "gl$, a /\ b));
printf(($" a or b: "gl$, a \/ b));
COMMENT
);
bitwise(BIN 255, BIN 170, 5)
)
Output:
bits shorths: +1 1 plus the number of extra SHORT BITS types
bits lengths: +3 1 plus the number of extra LONG BITS types
max bits: TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
long max bits: TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
long long max bits: TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
bits width: +32 The number of CHAR required to display BITS
long bits width: +116 The number of CHAR required to display LONG BITS
long long bits width: +209 The number of CHAR required to display LONG LONG BITS
bytes shorths: +1 1 plus the number of extra SHORT BYTES types
bytes lengths: +3 1 plus the number of extra LONG BYTES types
bytes width: +32 The number of CHAR required to display BYTES
long bytes width: +64 The number of CHAR required to display LONG BYTES
a: FFFFFFFFFFFFFFFFFFFFFFFFTTTTTTTT
b: FFFFFFFFFFFFFFFFFFFFFFFFTFTFTFTF
a and b: FFFFFFFFFFFFFFFFFFFFFFFFTFTFTFTF
a or b: FFFFFFFFFFFFFFFFFFFFFFFFTTTTTTTT
a xor b: FFFFFFFFFFFFFFFFFFFFFFFFFTFTFTFT
not b: TTTTTTTTTTTTTTTTTTTTTTTTFFFFFFFF
a shl 5: FFFFFFFFFFFFFFFFFFFTTTTTTTTFFFFF
a shr 5: FFFFFFFFFFFFFFFFFFFFFFFFFFFFFTTT
a rol 5: FFFFFFFFFFFFFFFFFFFTTTTTTTTFFFFF
a ror 5: TTTTTFFFFFFFFFFFFFFFFFFFFFFFFTTT
BASIC
QuickBasic does not have shift or rotate operations defined. Here are the logical operations:
SUB bitwise (a, b) PRINT a AND b PRINT a OR b PRINT a XOR b PRINT NOT a END SUB
FreeBASIC does not have rotate operators. Shift Right operator performs arithmetic shift if the left value is signed number and logical shift if the left value is unsigned number.
SUB bitwise (a AS Integer, b AS Integer) DIM u AS UInteger PRINT "a AND b = "; a AND b PRINT "a OR b = "; a OR b PRINT "a XOR b = "; a XOR b PRINT "NOT a = "; NOT a PRINT "a SHL b = "; a SHL b PRINT "a SHR b (arithmetic) = "; a SHR b u = a PRINT "a SHR b (logical) = "; u SHR b END SUB
C
<c>void bitwise(int a, int b) {
printf("a and b: %d\n", a & b);
printf("a or b: %d\n", a | b);
printf("a xor b: %d\n", a ^ b);
printf("not a: %d\n", ~a);
printf("a << n: %d\n", a << b); /* left shift */
printf("a >> n: %d\n", a >> b); /* on most platforms: arithmetic right shift */
/* convert the signed integer into unsigned, so it will perform logical shift */
unsigned int c = a;
printf("c >> b: %d\n", c >> b); /* logical right shift */
}</c>
D
module bitwise ;
import std.stdio ;
void testbit(int a, int b) {
writefln("Input: a = %3d , b = %3d", a, b) ;
writefln("AND : %8b & %08b = %032b (%4d)", a, b, a & b, a & b) ;
writefln(" OR : %8b | %08b = %032b (%4d)", a, b, a | b, a | b) ;
writefln("XOR : %8b ^ %08b = %032b (%4d)", a, b, a ^ b, a ^ b) ;
writefln("NOT : %8s ~ %08b = %032b (%4d)", "", a, ~a, ~a) ;
}
void main() {
int a = 0b11111111 ; // bit literal 255
int b = 0b10101010 ; // bit literal 170
testbit(a,b) ;
}Output:
Input: a = 255 , b = 170 AND : 11111111 & 10101010 = 00000000000000000000000010101010 ( 170) OR : 11111111 | 10101010 = 00000000000000000000000011111111 ( 255) XOR : 11111111 ^ 10101010 = 00000000000000000000000001010101 ( 85) NOT : ~ 11111111 = 11111111111111111111111100000000 (-256)
Forth
: arshift 0 ?do 2/ loop ; \ 2/ is an arithmetic shift right by one bit (2* shifts left one bit) : bitwise ( a b -- ) cr ." a = " over . ." b = " dup . cr ." a and b = " 2dup and . cr ." a or b = " 2dup or . cr ." a xor b = " 2dup xor . cr ." not a = " over invert . cr ." a shl b = " 2dup lshift . cr ." a shr b = " 2dup rshift . cr ." a ashr b = " 2dup arshift . 2drop ;
Rotation is not standard, but may be provided in particular Forth implementations, or as an assembly instruction in CODE words.
Fortran
In ISO Fortran 90 and later the following BIT INTRINSIC functions are defined:
integer :: i, j = -1, k = 42
logical :: a
i = bit_size(j) ! returns the number of bits in the given INTEGER variable
! bitwise boolean operations on integers
i = iand(k, j) ! returns bitwise AND of K and J
i = ior(k, j) ! returns bitwise OR of K and J
i = ieor(k, j) ! returns bitwise EXCLUSIVE OR of K and J
i = not(j) ! returns bitwise NOT of J
! single-bit integer/logical operations (bit positions are zero-based)
a = btest(i, 4) ! returns logical .TRUE. if bit position 4 of I is 1, .FALSE. if 0
i = ibclr(k, 8) ! returns value of K with 8th bit position "cleared" (set to 0)
i = ibset(k, 13) ! returns value of K with 13th bit position "set" (set to 1)
! multi-bit integer operations
i = ishft(k, j) ! returns value of K shifted by J bit positions, with ZERO fill
! (right shift if J < 0 and left shift if J > 0).
i = ishftc(k, j) ! returns value of K shifted CIRCULARLY by J bit positions
! (right circular shift if J < 0 and left if J > 0)
i = ishftc(k, j, 20) ! returns value as before except that ONLY the 20 lowest order
! (rightmost) bits are circularly shifted
i = ibits(k, 7, 8) ! extracts 8 contiguous bits from K starting at position 7 and
! returns them as the rightmost bits of an otherwise
! zero-filled integer. For non-negative K this is
! arithmetically equivalent to: MOD((K / 2**7), 2**8)
The following INTRINSIC ELEMENTAL SUBROUTINE is also defined:
call mvbits(k, 2, 4, j, 0) ! copy a sequence of 4 bits from k starting at bit 2 into j starting at bit 0
Haskell
The operations in Data.Bits work on Int, Integer, and any of the sized integer and word types.
import Data.Bits a = 255 b = 170 print $ a .&. b print $ a .|. b print $ a `xor` b print $ complement a print $ shiftL a b -- left shift print $ shiftR a b -- arithmetic right shift print $ shift a b -- You can also use the "unified" shift function; positive is for left shift, negative is for right shift print $ shift a (-b) print $ rotateL a b -- rotate left print $ rotateR a b -- rotate right print $ rotate a b -- You can also use the "unified" rotate function; positive is for left rotate, negative is for right rotate print $ rotate a (-b)
J
Actual calculations occur in bwo and brs. Other definitions provide formatting.
bwo =: 17 b. , 23 b. , 22 b. , 28 b.
brs =: 33 b.~ , (33 b.~ -), (34 b.~ -), 32 b.~ , (32 b.~ -)
boolf =: title"_ combine bwo, brs
combine =: ,. ":@|:@,:
t =. >;._2 'Bitwise x AND y: |Bitwise x OR y:|Bitwise x XOR y:|Bitwise NOT-x:|'
title=: t,>;._2'Left shift:|Right shift:|Right signed shift:|Left rotate:|Right rotate:|'
f=: (32#2)&#: { '.x'"_
Examples of execution, with output:
_255 bwo 5 NB. numeric output of bitwise operations 1 _251 _252 254 _255 brs 5 NB. numeric output of boolean rotation and shift operations _8160 134217720 _8 _8129 268435448 _255 boolf 5 NB. formatted text with English titling Bitwise x AND y: 1 Bitwise x OR y: _251 Bitwise x XOR y: _252 Bitwise NOT-x: 254 Left shift: _8160 Right shift: 134217720 Right signed shift: _8 Left rotate: _8129 Right rotate: 268435448 f _255 (bwo, brs) 5 NB. 32-bit diagrams ...............................x xxxxxxxxxxxxxxxxxxxxxxxx.....x.x xxxxxxxxxxxxxxxxxxxxxxxx.....x.. ........................xxxxxxx. xxxxxxxxxxxxxxxxxxx.......x..... .....xxxxxxxxxxxxxxxxxxxxxxxx... xxxxxxxxxxxxxxxxxxxxxxxxxxxxx... xxxxxxxxxxxxxxxxxxx.......xxxxxx ....xxxxxxxxxxxxxxxxxxxxxxxxx...
Java
<java>public static void bitwise(int a, int b){
System.out.println("a AND b: " + (a & b));
System.out.println("a OR b: "+ (a | b));
System.out.println("a XOR b: "+ (a ^ b));
System.out.println("NOT a: " + ~a);
System.out.println("a << b: " + (a << b)); // left shift
System.out.println("a >> b: " + (a >> b)); // arithmetic right shift
System.out.println("a >>> b: " + (a >>> b)); // logical right shift
System.out.println("a rol b: " + Integer.rotateLeft(a, b)); //rotate left
System.out.println("a ror b: " + Integer.rotateRight(a, b)); //rotate right
}</java> All of these operations may be combined with the = operator to save space. For example, the following lines each do the same thing: <java>a <<= 3; a = a << 3; a *= 8; //2 * 2 * 2 = 8 a = a * 8;</java>
JavaScript
<javascript>function bitwise(a, b){
alert("a AND b: " + (a & b));
alert("a OR b: "+ (a | b));
alert("a XOR b: "+ (a ^ b));
alert("NOT a: " + ~a);
alert("a << b: " + (a << b)); // left shift
alert("a >> b: " + (a >> b)); // arithmetic right shift
alert("a >>> b: " + (a >>> b)); // logical right shift
}</javascript>
Logo
to bitwise :a :b (print [a and b:] BitAnd :a :b) (print [a or b:] BitOr :a :b) (print [a xor b:] BitXor :a :b) (print [not a:] BitNot :a) ; shifts are to the left if positive, to the right if negative (print [a lshift b:] LShift :a :b) (print [a lshift -b:] LShift :a minus :b) (print [-a ashift -b:] AShift minus :a minus :b) end bitwise 255 5
The output of this program is:
a and b: 5 a or b: 255 a xor b: 250 not a: -256 a lshift b: 8160 a lshift -b: 7 -a ashift -b: -8
LSE64
over : 2 pick 2dup : over over bitwise : \ " A=" ,t over ,h sp " B=" ,t dup ,h nl \ " A and B=" ,t 2dup & ,h nl \ " A or B=" ,t 2dup | ,h nl \ " A xor B=" ,t over ^ ,h nl \ " not A=" ,t ~ ,h nl \ a \ 7 bitwise # hex literals
MAXScript
fn bitwise a b =
(
format "a and b: %\n" (bit.and a b)
format "a or b: %\n" (bit.or a b)
format "a xor b: %\n" (bit.xor a b)
format "not a: %\n" (bit.not a)
format "Left shift a: %\n" (bit.shift a b)
format "Right shift a: %\n" (bit.shift a -b)
)
bitwise 255 170
MAXScript doesn't have arithmetic shift or rotate operations.
OCaml
<ocaml>let bitwise a b =
Printf.printf "a and b: %d\n" (a land b); Printf.printf "a or b: %d\n" (a lor b); Printf.printf "a xor b: %d\n" (a lxor b); Printf.printf "not a: %d\n" (lnot a); Printf.printf "a lsl b: %d\n" (a lsl b); (* left shift *) Printf.printf "a asr b: %d\n" (a asr b); (* arithmetic right shift *) Printf.printf "a lsr b: %d\n" (a lsr b); (* logical right shift *)
- </ocaml>
Perl
<perl>use integer;
sub bitwise($$) {
($a, $b) = @_; print 'a and b: '. ($a & $b) ."\n"; print 'a or b: '. ($a | $b) ."\n"; print 'a xor b: '. ($a ^ $b) ."\n"; print 'not a: '. (~$a) ."\n"; print 'a >> b: ', $a >> $b, "\n"; # logical right shift
use integer; # "use integer" enables bitwise operations to return signed ints print "after use integer:\n"; print 'a << b: ', $a << $b, "\n"; # left shift print 'a >> b: ', $a >> $b, "\n"; # arithmetic right shift
}</perl>
PHP
<php>function bitwise($a, $b) {
echo '$a AND $b: ', $a & $b, "\n"; echo '$a OR $b: ', $a | $b, "\n"; echo '$a XOR $b: ', $a ^ $b, "\n"; echo 'NOT $a: ', ~$a, "\n"; echo '$a << $b: ', $a << $b, "\n"; // left shift echo '$a >> $b: ', $a >> $b, "\n"; // arithmetic right shift
}</php>
Pop11
define bitwise(a, b);
printf(a && b, 'a and b = %p\n');
printf(a || b, 'a or b = %p\n');
printf(a ||/& b, 'a xor b = %p\n');
printf(~~ a, 'not a = %p\n');
printf(a << b, 'left shift of a by b = %p\n');
printf(a >> b, 'arithmetic right shift of a by b = %p\n');
enddefine;
Conceptually in Pop11 integers have infinite precision, in particular negative numbers conceptually have infinitely many leading 1's in two's complement notation. Hence, logical right shift is not defined. If needed, logical right shift can be simulated by masking high order bits.
Similarly, on infinitely precise numbers rotation is undefined.
Python
<python>def bitwise(a, b):
print 'a and b: ' + str(a & b)
print 'a or b: ' + str(a | b)
print 'a xor b: ' + str(a ^ b)
print 'not a: ' + str(~a)
print 'a << b:', a << b # left shift
print 'a >> b:', a >> b # arithmetic right shift</python>
Python does not have built in rotate or logical right shift operations.
Smalltalk
Since GNU Smalltalk by default runs without a graphical user interface, I wrote the program in that dialect. The actual methods for bitwise operations (bitAnd:, etc.) are the same in all implementations.
a := stdin nextLine asInteger.
b := stdin nextLine asInteger.
('a and b: %1' % {a bitAnd: b}) displayNl.
('a or b: %1' % {a bitOr: b}) displayNl.
('a xor b: %1' % {a bitXor: b}) displayNl.
('not a: %1' % {a bitInvert}) displayNl.