Normally, if the constraint we're interested in is the length of the number in bits rather than the value of the number or the size/length of some data structure, we simply define N to be the length of the number and express big-O in terms of that. So I would say that your operations are O(n) or linear time and be sure to mention somewhere that n is the length of the key as opposed to the value of the key or the number of nodes already inserted or whatever.
This is most often done in the context of integer factorization. Whenever someone tells you that we have yet to find a polynomial-time algorithm for finding the prime factorization of an integer, they're talking about time complexity where N is defined as the length of the integer. If you instead define N as the value of the integer, the obvious brute force algorithm of simply trying all possible factors is obviously a polynomial time solution. This is sometimes called pseudo-polynomial time. So I suppose you could say your operations run in "pseudo-logarithmic time" if you really wanted to.
If you're wondering why we do this, the main reasons I'm aware of are that 1) The convention for big-O is that n always denotes "the length/size of the input", whether that input happens to be a tree with 50 nodes or an integer 50 digits long. So it's not as arbitrary as it might seem. 2) In practice the length/size of the input seems to be the limiting factor. The fact that I know a pseudo-polynomial time algorithm for prime factorization does not change the fact that I'll never be able to brute force an RSA private key with my laptop.